Weeeell, actually, we did some more poking today, and found that the average speed of travel (at least on Dwilight) is around 15 miles/hour.
According to Wikipedia, the speed of a standard march is approximately 3.5 miles/hour. A double-time march is 1.5x that, for around 5 mph.
It would take a horse at a fast trot to make 15 mph, and I don't think a horse can manage that for 8 hours straight with a noble and all his baggage, or with a couple of soldiers on it.
BM characters are no sissies! They can sleep walk at over 15mph!