The target AFRs also have a lot to do with the combustion byproducts as well. Ideally, we'd get CO2, H2O and heat from breaking down the fuel during combustion. However, it we run too hot or too cold (or incomplete burns, etc), we get some nasty byproducts such as partially broken HC chains, NOx, and CO.
Running lean also creates more heat (more fuel+more oxidizer=more heat+more power). In modern engines, we use fuel to also act as a cooling agent WHILE heating the air/fuel mix to help combustion. If we ran a modern, mostly aluminum engine at 1500F constant temperatures (from exhaust gases), things start to become.... soft.
Water (or coolant injection) in this case is a nice "volume expander". Water (and water-based compounds) can expand exponentially when heated (like water steam can expand to 200x it's liquid water's previous volume). This increase in pressure translates to more force, substituting fuel explosion as steam explosion. This in turn uses less fuel for the same result.
Anywho, the fuel economy may suffer slightly, but this is a case of "killing the calf to save the herd".