I think the Romans largely managed it through building level roads to march on. Most pre-industrial armies were marching off-road. I would be saying walking 2 miles/hour on a tarmac road would be someone's maximum before causing damage. Offroad I'd be saying 1.5, maybe even 1 mile/hour depending on the terrain.