How could he have fueled properly for that effort?

Clearly, he didn't.

It's hard to get specifics, but that doesn't seem impossible for a pre-industrial, highly trained runner (several hunter-gatherer tribes seem to be capable of those sorts of distances over multiple days, and he was as close to a professional distance runner as existed at the time). Remember also that he isn't running through uninhabited territory; there would likely have been multiple opportunities (pre-established supply depots? well-known locals?) where an official representative of a major local power would have been able to acquire food.