I know you said that they aren't strict carnivores, but if you wanted to look at how livestock can provide the calories needed, here you go.
1 kg of meat will provide between 2100-2300 calories (specific amounts depend on the type/cut of meat. This is looking at beef, pork, and chicken). According to this website, an average cow provides 530 lbs of usable meat. That's about 240 kg of beef. Let's round up to 250 kg, to account for parts of the cow that most people now aren't willing to eat, but that your soldiers might (brain/eyes/etc).
Assuming that the soldier needs about 2300 calories for a day (this is probably low), one cow will feed 250 soldiers for one day. That means 4,000 cows ought to feed your whole army per day.
One hog should provide about 75 kg of meat. So you'd need about 13,000 hogs per day.
A chicken provides about 2.5 kg of meat. You'd need about 400,000 chickens.
For the sake of this example, if you were to feed your whole army for a 3 month campaign only on live cattle that they bring along, they'd need 202,105 acres of grazing land. Formula came from here. Alternatively, if you were to bring along the fodder yourself (like grain and alfafa), you'd need 9,600 tons of it.
I'm not necessarily endorsing this solution, but if you had the land you could do it...but ideally, your army will take along with it some mix of livestock, preserved meats, vegetables, grains, as well as eat whatever they can hunt/forage/pillage.
I know these figures, as well as the figures that Samuel provided, sound ridiculously high. But considering your army is so large, the population of the empire must be enormous. If you scale everything up, including farmland and livestock necessary in order to sustain this population, then this isn't out of the question. Also, I'm assuming your entire army isn't going to be in all the same place at once. If they're divided up into several smaller companies (this is very much recommended), fighting on different fronts, then it's not completely unreasonable to imagine them hauling around the food they need.
Bonus: animal by-products. I haven't taken into account milk from cows, or eggs from hens, or all the broth you could make from their bones. But assuming your 400,000 chickens lay 400,000 eggs, you could feed about 13,000 soldiers just from their eggs alone.
If your 4,000 cows are producing, let's say, 6 gallons of milk per day, you could feed about 27,000 soldiers from the milk/cream/butter from the cows.