new tires=bad gas mileage

In any case you should :
Inflate your tires to whatever they say say 35 psi cold.
Find a 10 or more mile stretch of highway with mile markers.
Note your mileage on your odometer
Drive to the tenth mile and check your odometer.

if it is far off calculate the percentage difference, pull your odometer gear out of your trans and go get one that is the correct number.

Example :
If your are 10 percent high on your odo You read 11 miles after driving 10 miles.
Your gear is 10% too small and you need to get one %10 larger.

If your are 10 percent low on your odo You read 9.1 miles after driving 10 miles.
Your gear is 10% too large and you need to get one %10 smaller.

Replace your gear and retest
Or you can go to a speedo shop if you can find one.