I would do it by doing a detailed takeoff, and then putting both labor and material prices to that takeoff. For example:
Clearing site and excavate for footings; level for floor: $1500
Calculate cubic yards of concrete, figure at $350/cy: in your case: 136' x 4.5' /27 = 23 cy x 350 = $8000 footing cost.
Calculate floor cost: .33' x 38 x 30 x $400 = $5600
Exterior Sheathing: 136 x 12' high /32 = 50 sheets x $18 = $900
Exterior Studs: 136 /1.25 = 110 studs x $10.93 = $12
Roofing: 42 x 34 x 1.15 = 17 squares at $350 = $5800 roofing
etc, etc, etc. add about 10 to 15% to your materials for waste. Make a guess at the labor for the framing and such.
Another way is to take a generic $ per square foot, as ducksface has put out there. That works if you have good values for your local area, and your job is just like the jobs those values came from.
For a comparison, I'm building a house in eastern Oregon at the moment. I am the general contractor on it, and doing a lot of the work myself. Attached to that house is a 36x48 3 car garage. 11 foot ceilings with scissor trusses going up to about 16 in the center. back 18 foot is 2 story using attic trusses for a 14 foot wide attic. Construction is 2x6 frame, hardi-plank, architectural shingles. Three single wide doors, two at 8 foot and one at 11. I did the footings for the garage myself, and doing the finish work. I paid to have it framed. Did the roof prep, and paid to have it shingled. Bought the doors for half price from someone that had ordered wrong size. Backfilled and compacted the gravel under the floor myself. Will place the rebar and hydronic heat piping and foam myself, but pay to have the concrete placed. My estimate sheet, which is about 95% complete with either completed work, purchases, or bids at this point is at about $68,000. That does not include the driveway which I will do myself with paver; that would easily be another $8K. That does include contracting the sheetrock; if I do that myself it will save me about $5000. I'm doing the electrical myself, and the interior framing, the insulating, the hydronic heat, the garage door installs, the painting, the trim. The things that I contracted out are the rough framing, the roof shingles, the concrete floor placement/finish, the siding, and digging the footing trenches. All the rest of the labor is mine; the materials are a large part of it.
A fully finished, quality shop is expensive. Even scrounging for cheap materials and doing almost all the labor myself, I'll be into mine about $40 per square foot. The $20 per square foot numbers you seen out there are either bare bones pole barn type buildings with owner labor, or delusional.
I'd usually estimate $65 to $85 for a 2 story unfinished garage/shop, with electrical and concrete driveway. I"d push that up to about $110 for a finished space.
In your case, that'd equate to $74,000 to $96,000; so your bid was in the right range.
Your concrete seems low, but the demo seems high. For that cost, I'd buy a concrete saw, prybar, sledgehammer and jackhammer and do it myself. 3 weeks evenings and weekends and you would earn about $6000; the $4000 would go to haul away costs and tools. Add $1000 of rental for a bobcat and it'd be a lot easier. I pay about $250 a day to rent it for a half day Saturday and all day Sunday. You can get roll off dumpsters to haul the debris away; just don't fill them too full. I demo'd out a septic tank, a 16 x 6 foundation wall and footings, and a 6 x 8 footing by hand on my house, I had under 8 hours total in it, and paid $450 to haul away the debris. That 8 hours was in about 6 sessions; it's hard on an old man to swing a 12 pound hammer for very long.
A third way is to just get quotes from 3 or 4 contractors, and see how they compare out.
The answer to the question you didn't ask is that a shop is just plain expensive, either in dollars or in your own time and skilled labor, or in both. Most of us are deluding ourselves if we think it is cost effective to build these larger garages/shops to do a few car repairs or projects. It's an expensive hobby.
