As @LynnCrumbling stated, this would be hard to put a number on, mainly because it depends on too many factors. This is what I can tell you. When O2 sensors get old, they don't necessarily go bad, what they do is get lazy. When a good O2 sensor is doing its thing, if you were to look at the readings from it, the numbers go all over the place, from top of the range to bottom of the range and everywhere in between. As the sensor gets old, this jumping of numbers slows down. This is called getting lazy. The lazier the sensor gets, the worse your gas mileage may become, due mainly to the fact that the computer can only go on the information which is given it. I'm not sure if it would drop as much as you're talking in your case, but it will drop. When I say drop, it's not a drastic thing. It will just get worse and worse over time, until it gets to the point where you say, "I'm currently getting 19.6mpg ..." and they'll do all of this without throwing a code on your computer.
Like I said, I cannot tell you by how much it will increase, but if they are as old as you say, with the mileage you are talking about, I'd say they are way over due. Most manufacturers recommend O2 replacement every 100k miles. The need for changing the O2 sensors is pretty much a given at this point.