I have done both swaps ... C4 to AOD, and C4 to Tremek TKO-600.
I cannot tell you what the increase in mileage was, though, because I don't know what it was before the swap. Also, in both cases, the engine was replaced at the same time as the swap, and the rear gears, so comparing before/after mileage is apples to oranges.
I can tell you, though, that my '66 with a 289/AOD combo and 3.50 9" rear, I have achieved 22 mpg. This car runs consistent 14.3's @ 101 mph. It would probably get better mileage, had I gone with a lock-up converter.
In my '69, the 408/TKO-600, I have been able to achieve 17mpg. I figure that's pretty darned good for a carburetted, big cubic inch engine, with 354 RWHP and 416 ft. lbs. of torque (so far, best run is 13.03 @ 117mph with a TON of tire spin *LOL*).