It varies a bit and experience matters as a more experinced tech can crank out the same reg at an equal or higher level of quality much faster than a relatively new tech.
Most regs (first,second, and octo) can be done in about an hour, but a really dirty or encrusted, corroded reg can take longer. A very simple reg like a flow by piston reg and unbalanced downstream second stage like an SP Mk 2 R190 or Aqualung Calypso can usually be done in a lot less than 1 hour.
O2 cleaning adds additonal time as does any more involved work that may be needed to replace parts not normally done during a normal annual service (flow vane o-rings, etc). If the reg has not be serviced recently or regularly, the odds are that more labor, some times a lot more labor, will be required to service it. From a tech perspective, regs you service all the time go much faster while less common regs that you only see one or two of per year, will take you a bit longer given the need to refer to schematics, look up part and o-ring numbers etc. Most shops however charge a flat rate regardless of dirt, condition or relative rarity, so the tech pretty much counts on everything averaging out at about an hour each.
Turn around time itself depends on how often the shop's tech(s) work(s) and how many regs need serviced in a given week. For example I come in each Saturday so if you drop the reg off on Saturday morning, you'll probably have it same day, if you drop it off on Monday, it's more like 5 days. When it gets eally busy, I bring the surplus home and do them in the evenings during the week (I have a bench and test equipment at home as well) so the turn around still will not be worse than a week.
Labor tends to get more expensive near salt water but should not exceed about $25.00 per stage. Given our geographic location in essentially the geographic center of the North American continent about as far from salt water as it is possible to get, our rates are dirt cheap at $30 for a first, second, octo combination (basically $10.00 per stage.) I get half so that means I only make about $15.00 per hour. The saving grace here is that I get everything at cost in terms of equipment, O2, hydro tests, etc so I just leave the money on account with the shop which basically doubles the value of what I am paid to about $30 per hour. It ends up being a good deal for me, a good deal for the shop and a good deal for the customer.
When regs come in, the customer is asked when they need it, so some prioritizing can be done to ensure someone leaving on a trip will have it in time while someone who will not be diving for a couple months will probably go to the bottom of the list.