According to The Atlas of Middle-earth, they were running at three miles per hour.
In The Atlas of Middle-earth, Karen Wynn Fonstad, charts out how much every character travelled on each day. Her conclusions were that Aragorn, Legolas, and Gimli were running at three miles per hour.
In The Lord of the Rings, unlike The Hobbit, Tolkien gave considerable information about distances covered, time spent in travel, and campsite locations. Hundreds of clues gleaned from the story and the appendices provided the data for not only these pathway maps, but also the base maps themselves. Stated distances occasionally differed from those shown on Tolkien's maps, so the maps were altered slightly to more closely agree with the text. Complete agreement was not always possible, however, so the distances shown along pathways may sometimes not measure exactly the same on the accompanying scale; but they do agree with the text or with estimates made from its passages, using three miles per league as suggested by Tolkien. When mileages were not listed for a day or several days, they were estimated by measuring the distance on Tolkien's map along the route between known campsites, and dividing it equally between the days (allowing for stated variations, such as longer hours in travel or faster or slower speed). To determine if the various estimates seemed reasonable in relation to each other and to the Primary World, a table was compiled to allow comparison. Although a few of the rates of travel seemed unusually fast or slow (for reasons explained with the related maps), most appeared to be fairly consistent when allowing for such variables as rugged terrain, need for haste, and physical or psychological hindrances. When one day's journey had distinct stages these were listed individually. Most of the journeys were on foot, with occasional rides on boats or horses. The range of speeds in general were:
Walking — Most commonly, about 2.0 to 2.5 mph (24 to 30 minutes per mile) was maintained, but rose to 3.0 mph (20 minutes per mile) run by the Orcs and their pursuers; Aragorn, Gimli, and Legolas.
Riding — Ponies: 3.4 mph, jogging (17.6 minutes per mile). Horses of Rohan: 6.7 mph, galloping (9.0 minutes per mile). Horses of the Dunedain: 7.0 mph, galloping (8.6 minutes per mile). Shadowfax: 20 mph, galloping (3.0 minutes per mile).
Boating — Small boats with the current: drifting, 2.8 mph (21.4 minutes per mile); paddling, 4.1 mph (14.6 minutes per mile). Ships against the current: rowing, 4.7 mph (12.8 minutes per mile); sailing, 7.2 mph (8.3 minutes per mile).
The Atlas of Middle-earth - Pathways
Fonstad calculates the specific dates and distances as such:
Rauros to Isengard — Aragorn, Legolas, Gimli
Date Hours Mileage MPH Comments Campsite
F.26-27 14,12 27,36 1.9,3.0 Late afternoon to dusk Halfway to Entwash
day. Hills, then plain.
F.28 12 36 3.0 South of Downs
F.29 12 36 3.0 Reach Downs about 11AM. North end of Downs
F.30 5.5 30 5.5 Afternoon on horseback. Edge of Fangorn
The Atlas of Middle-earth - Pathways
It should also be noted that Tolkien's knowledge of travel rates was based on his military training. He has elsewhere made reference to this in his notes.
We are not dealing with the movements of human cavalry with its slow pace (except in action): e.g., “walk” 3½ mph; “trot-walk” 5; “trot” 7, etc.! Elves (and their horses) were swifter in movement, hardier, and of greater endurance.
[Editor:] In associated draft material, Tolkien attributes these figures to “FSP” – i.e., the Field Service Pocket Book, which he would have been issued during his military training prior to being deployed to France in 1916. Both the 1914 and 1916 editions cite precisely these gaits and speeds on p.37.
The Nature of Middle-earth - "Elvish Journeys on Horseback"