the reason you getting crappy mileage is your O2 sensors are not getting the correct reading form the cat delete, causing your ECU to put in more fuel, it's trying to get to the correct readings. probably why you're getting a SES code.
i have supersprint headers and i had the same thing, low gas mileage, engine ran erratic, plus SES code. to get rid of all that i put in O2 simulator, the engine really came alive, exhaust tone was louder, ran smoother and gas mileage back to normal. i never ran anything less than 92 oct though.