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.
Other answers are right, but I'd like to add that an invading army horses don't just eat grass: they can also eat the crops that otherwise would have feed the invaded human population. That is, an invading army can feed its horses on wheat or barley on invaded land. A consequence of that is that the invaded population is likely to starve for a year, but that is not expected to be the main concern of the invading army.
In addition, grass yields from other answer assume the annual yield of steppe, but the annual yield of an steppe is not likely to be in the field at any given time because pastures are grazed year round - or at least in the favorable season. However, cereal fields are recollected once a year and therefore if the attack is properly timed invaders do have the complete annual yield at their disposal.
These Mongol horses of the steppe, early domesticates, tarpans, really, also provided milk for the cavalrymen, requiring significant added forage for lactation nutrition demands, which are quite high, given the high nutritional value of the milk.
Milk mares likely were not ridden, and there must have been foals, or perhaps the foals were weaned early (most can survive readily without nursing after a month of age), or eaten. The lactating mares continued lactating due to thrice daily milking, drank readily by the horsemen. Lactation can persist through the year, provided nutrition is adequate, lots of water, salt, and forage required.
As noted, these horse people knew grass, and where the best horse milk grass grew. The steppe grass nourished the horses, year round, it seems, and the grass-nourished horses fed the humans milk and meat in addition to providing transport. Campaigns must have been seasonal, so seasonal is the horse. When the grass is in season, conquest with horses is in season. The longest days provided the longest travel, shorter days, not so much conquest.