It's not too much of a stretch to assume Data has some-sort-of reactor in him, maybe a cold Fusion one. It's also
possible he does run on "batteries" but the type of battery/powercell that phasers work on. Consider that phasers have the energy to cause beams or explosions that can utterly destroy
things. It's suggested at one point and overloaded phaser has to potential to take out a deck of the ship, we've seen them destroy and heat rocks, and vaporize creatures in seconds (in of itself requiring enormous levels of energy.) So it's not too much of a stretch to think data has these power cells in him and they're able to run him quite well. Any "recharging" needed could be done by "food" he ingests, mechanical recharging as he moves, or the absorption of energy as he exposed to things like light and forms of radiation.