The cost depends on the labor and equipment rates in your area. However, I can tell you that the deepest 9" of excavation is a LOT more expensive than the first 9"! Due to OSHA regulations, the trench must be wider, depending on soil type. So, you are not just excavating the 9" in the bottom of the trench, but also the sides of the trench. More excavated material, means more backfilling.
The backhoe needs to reach deeper for both excavting and setting the pipe. So, the added cost involved is not just for the digging, but for the setting of the pipe too.
Here in the midwest, excavation at that depth would be something like $15.00 to $18.00 per cubic yard out and backfilling with on site materials would be $6.00 - $8.50 back in, uncompacted. Here Operating Engineers get $48.00/hr and a large backhoe is about $95.00/hr.
It sounds like you are in a dispute with the contractor. Doesn't your contract have unit prices to go by?
Good luck.