Note 1 : I will use SI units for my calculation
Note 2 : I assume that water will not be a problem and that your army will always found a river or lake. Also I assume that your army will be disbanded after reaching the objective, not taking in account the need for them to go back afterwards.
First of all, the humanitarian daily ration weights 850 g. Since it is optimised with modern technologies, I think that a 1 kg daily ration is a reasonable estimation of the weight of a medieval ration.
If each soldier carry its own supply, your are only limited by the weight they can carry in addition to their usual equipment. If soldiers can carry 10 kg of supply without being crippled, it means 10 days of autonomy. Of course you have to gather the starting supply first, but with that logic you can gather it as the same time you gather your army, since your men carry their supply. It means that at peace time you should keep your (potential) army dispersed through the land.
Then, you want to march 500 miles (800 km). By assuming that your army walks 8 hours a day at a speed of 5 km/h (only possible if you have good roads), it will take you 20 days to reach your destination (not that this is the best you can do, the real number will probably be much smaller, for example if your roads are not that good or if you are in unknown territory).
Therefore with the most optimistic estimation, you can only travel half the plan distance with the "self carrying supply" method.
Note : if your army fully rely on horses, as the Mongolian one, you are both faster and able to carry more stuff. But I focus here on marching army.
If you want to carry the supply, it becomes a nightmare very rapidly. For the 10 days remaining and a 10 000 men army, you have to gather and carry 100 metric tons of food (without taking in account the additional men and animals needed to carry it). It does not look very practical.
You can not really send the supply to your army, since it would need to travel faster than your army. If you have a faster way to travel, your army should probably us it. But if your army need to stay somewhere, it is a good idea.
In the other hand, you could use "walking supply" such as living cow. Since a cow can be estimated to weight around 500 kg (the estimation given in the link is higher, but medieval cow were probably lighter), only 200 cows are needed for 10'000 men and a 10 days march, this seems reasonable. They can even carry stuff with them and you can milk them. Well you still need to feed them, and they can be quite slow (I doubt they will walk 8 hours a day), thus expanding the time you need to reach your destination.
All this together makes that you can probably not go further than 50 000 men with this strategy (already at least 1 000 cows are needed).
Note : if you are a Mongol you can simply milk and eat your horses
You can still eat what you find on your way. Hunting does not seem efficient, since most of your time will be dedicated to walk toward your objective.
However using the supply gathered in the towns and village you pass by is quick and give you plenty of food (you have an army, you can seize what you need if the people do not want to give it to you). If there is a 30 days reserve of food, it means that each inhabitant of the land you go through can "provide" supply for 30 soldiers (and afterwards starve to death).
I think this is the really limiting factor. By travelling through a very populated area, you can handle a very big army. Going to a 10 000 inhabitants town each day let you feed 300 000 soldiers (with our assumptions). Actually this was the main strategy used during medieval times, and it explains why war did cause such terrible famines and destruction : armies just scavenged what they needed.
Note : if you reign over a big empire, storing food everywhere in large quantity help the movement of your troops.
In conclusion, the maximum size of your army is defined by the population and the wealth of the land through which you are travelling, other possibilities being viable only for a short period.