here in New York City which the attorney fee is sort of higher than nearby area, it's charged $4,000 - $5,000 in average, for your situation (a couple w/ no kids go through 140 and 485). Considering H-1 you mentioned, it would be no more than $1,000 in extra.
Please be advised, that Filing fee are additional.
Please be advised, attorney fees do varies by locations.
I tend to believe you were nailed, for spending over $10k, with filing fee in addition.
Please read your representation agreement.
Please read this also http://web.wenxuecity.com/BBSView.php?SubID=immigration&MsgID=327339