http://www.academia.edu/5545172/Persistence_Hunting_by_Modern_Hunter_Gatherers
On foot for sure. There's not always an opportunity to corner an animal or do something else clever. Sometimes they had to just run them to exhaustion. Humans are pretty badass.
In the American west, there are almost always subtle (and in some cases not so subtle) topographic features which enable the capture or containment of herd animals if they can be driven into those features. Here, specifically, and in many of the areas I have been in, there are valleys and even box canyons which will do quite nicely. As an alternative, chasing the herd toward a cliff works, too, and the numerous identified buffalo jump sites across the west attest to this. Chasing some critter 20 km in the heat of the day may be a way to get (some damned gamey) meat, but there are more efficient means. The enclosure may not necessarily even be physical, if stationed hunters pop up from concealment and turn the herd or use fire to alter its movement. Terrain features that may not be apparent from the modern roadside exist and the hunters would know the area best to take advantage of those. One example you showed had a track that doubled back repeatedly. that could have been avoided through cooperation and coordination, and stationing hunters to block return routes. So, too, could a drive/stand technique where hunters wait in concealment along game trails while others drive the herd past (and spear the animals as they pass). It is a technique still used, even in the era of firearms.
Even sitting next to the trail to the water hole with a favorable wind beats running 20 km in the mid day heat. Humans get heat stroke, too.
There are far better techniques for hunting than chasing something down on foot, again, it is the ability of humans to out think their prey that made them an apex predator.
