The average horse eats 10-20 pounds per day, according to this pet website. Considering the fact that the horses may have to eat even more because of the hard traveling they had to endure, it's likely that food costs must have been incredible. Genghis Khan's army traveled an average of 14 miles (23 km) a day during the China campaigns, with some claiming they traveled 120 miles per day when 'charging towards a target'. In addition, each horseman kept 3-4 horses in tow.
Let's do the math: 100,000 mounted archers * 4 horses each * 10 kg/day * 250 days/campaign = 1,000,000,000 kg of forage required each campaign.
As noted here annual forage yield of meadow steppe is about 2000 kg/ha; of typical steppe about 900 kg/ha; and even desert steppe yields 200 kg/ha. Thus the area required to support Genghis's cavalry for a campaign ranges between 500,000 to 1,000,000 ha, or 5,000 to 10,000 km^2. A single day's forage could be found in an area of 20 to 40 km^2, which seems quite a reasonable campground size for an army of 100,000 cavalrymen.
Of course, given this forage requirement, it is no surprise that Genghis's army moved so rapidly - if it didn't it was going to starve.
Update: Genghis's army rode ponies, not full horses, reducing forage needs accordingly.
Let me rephrase - The Mongols (and other steppe peoples such as Manchus and Turks) rode breeds of horse that average a bit under the modern 14 hands height limit for a pony. Let's say typically 13 to 15 hands. This is about one hand shorter than the height of a typical riding horse, of 14 to 16 hands. As fuel requirement generally goes as the cube of height, ceteris paribus, a horse/pony only 14/15 as high would require about 20% less feed. Make it 15% less to allow for cooler temperatures and a consequently faster metabolism for the breed.
This is not really an answer to your question, but the following numbers look much more realistic.
In the Russian army at the beginning of XX century daily ration for horses consisted of 4 kg of oats, 4 kg of hay and 1.6 kg of straw. Since the Mongol horses didn't eat oats (nomads had no oats) ration should be counted as hay - 15 pounds (6 kg) of hay per day per horse, or 1 800 tons of hay for the whole the Mongol army. If we assume that there were minimum 2 cows in farm household, this is year supplies of 611 courtyards, or about 200 villages. And when you consider that in January, when the Mongols has moved across Rus', half of the feed stock has been eaten by cattle. It is necessary to take into consideration guerrilla war and Mongolian robberies that spoiled much of the forage. It would not be an exaggeration that for for one day Mongols needs supplies of about 1 500 courtyards.
According to archaeologists, in the XIII century 1 courtyard handles 8 hectares of land per year, ie, 1500 courtyards handles about 120 square kilometers of arable land. Arable land could not be more than 10% of all lands. Hence Mongol horde had to move every day about 40 km, and send on both sides of the route groups of foragers for 15 km. But the speed of the horde in Rus' is known, Russian historian Ivanin tells that speed was 15 km per day. Thus, a number that tells the historian Kargalov - 140 000 warriors with 300 000 horses - is unrealistic. It is easy to calculate that at a speed of 15 km per day could move the army which had only about 110 000 horses.
According to Dmitriy Chernyshevsky, Zhaksylyk Sabitov ("Questions of History and Archaeology of Western Kazakhstan")
Of course "thread" will cover much more area than "group". That means more steppe to feed horses. Let's say length of the army is 50km, and horses can go 2 km at most from the line to eat. Then it would cover 100km^2, and if army marches 23km a day, it would be 46km^2. Still sufficient. On the other hand, if they move in a dense group like rectangular then horse feeding is going to be problem as there are too many horses in less space. Also sparse much bigger rectangular group may lead to too much dust and soil devastation. So marching like "thread" is enforcement. Genghis Khan's army was full of cavalries. If there was more infantry like other nations, horses won't have problem of feeding in rectangular group.
Also Mongolian horse is kind of wild, it doesn't require much care like other horses(http://en.wikipedia.org/wiki/Mongolian_horse).
In Vasily Yan's "Bat khan" book, the army's maneuver explained in detail. Bat is grandson of Genghis Khan, apprentice of general Subotai. You may use the book as starting point to further investigation. Here's the google search results http://bit.ly/NSGCTt, book on Amazon http://amzn.to/1fFTiJD
I written quiet long post that doesn't fit in comment section, so dropped in answers.
Between 1211 and 1225—a period that neatly coincides with the rise of Genghis Khan and the Mongol empire—central Mongolia enjoyed a spell of sustained benign weather unlike anything the region has experienced during at least the past 1,100 years and probably much longer.
The long run of unusually good conditions meant abundant grasses and a huge increase in herds of livestock and war horses that became the basis of Mongol power—a marked contrast to the long and exceptionally severe droughts that gripped the region during the 1180s and 1190s, causing unrest and division.