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.