Summary
All else being equal, runners on Earth will accelerate harder up front, but runners on Mars will have higher top speeds. As such, longer runs will favor Mars, while shorter runs will favor Earth. Assuming you can breathe on Mars, or you're the Terminator and don't need to.
I suspect that initial acceleration will be more important, and Earth runners will win more, in races short enough to typically be considered "sprinting".
Basic Physics
There are three effects in play here before you get into human physiology.
First, Mars has no oxygen to breathe, so you'd have trouble running at all. Let's assume the person has a magical oxygen supply of negligible mass. We could also be talking about a battery-powered electric vehicle, android, etc.
Second, Mars has very little atmosphere, so you're not limited by air resistance nearly as much as on Earth. However, in dirt or gravel, rolling resistance can be a lot higher than air resistance, so this may not matter.
Third, Mars has less gravity, giving less traction, resulting in a lower maximum acceleration force. On a loose surface, you can dig in and push against the ground, but ultimately low gravity will make the dirt stick to the surface less, and still give you worse acceleration.
Compounding Factors
Going uphill means traction is more important. Gravity differences will tend to dominate, and Earth vehicles accelerate harder. Because there's now a rearward acceleration force (the vehicle's weight), maximum speed will be limited by the speed at which the acceleration force equals weight, which will be the dominating limit for humans or low-powered vehicles, or steep inclines.
Going downhill means traction is less important. There will be a point on the downhill where power is essentially irrelevant and traction just doesn't matter. At that point, lower gravity will accelerate at a lower rate, but lower air density on Mars means terminal velocity will be much higher.
On hard, flat surfaces, traction will be the main factor in initial acceleration, while air resistance will be the main factor in top speed.
In deep sand or other loose terrain, rolling resistance will dominate air resistance. On flat ground or uphill, Mars' lower gravity won't sink you into the ground as far, and you'll tend to do better there. There will be a particular downhill slope where the gravity pulling you forward is more important than that sinking you into the dirt, and you'll do better on Earth.
Running
A wheeled vehicle is different than feet moving across the ground, but the differences aren't really significant here. Feet will tend to dig into dirt better, but so will mudding tires. Tires are more efficient, but relative efficiencies are still worse in the same places. So we can treat running in much the same way we'd expect a low-powered vehicle to perform, as far as the foot-to-ground interface is concerned.
However, there is a major difference between humans and the vehicles we build: gearing. A bike or car can be re-geared for better acceleration or top speed as needed. A bike on Mars can have multiple gears to keep the rider near their maximum power at all speeds, resulting in both maximum acceleration and top speed (or close to it). A car can do the same.
But a human only has one "gear". Regardless of potential power output, there is a maximum speed we can twitch our legs back and forth. The linear speed of our feet at that frequency is the outside maximum we can run. For most humans, the issue is diminishing power output at higher frequencies, to the point where all the power expended is used to maintain that leg speed, and there's nothing left for acceleration. For Olympic-level sprinters, the speed of nerve impulses starts making it impossible to think about moving faster.
This means that even on a downhill stretch, maximum speed is limited. If we try to exceed that speed, we'll just tumble and hurt ourselves. It also means we very quickly get to a speed where we can't overcome traction, even in low gravity. As such, a lot of the issues above become irrelevant.
So on a downhill, we'll accelerate harder on Earth (better initial grip plus gravity accelerates us directly). Because Mars has lower gravity, less power is used fighting gravity and more is therefore available for moving our legs, so we'll go a little faster top speed. But probably not by much.
On an uphill, Mars will win at acceleration, because we're fighting gravity less. Earth might give better instantaneous acceleration because of the better grip, but after a step or two Mars will be in the lead. Mars will also win at top speed since less power is wasted fighting gravity.
On flat ground, Earth will win off the line and hold the lead on speed for a while. Both places will have similar top speeds, so Earth will tend to win because of the initial distance gains. However, Mars still requires less wasted energy fighting gravity, so top speed will again be higher.
Conclusion
A runner on Earth will get a better acceleration off the line, but lower top speed. A Mars runner will win if the race is long enough. The more downhill the race, the longer it will take before the top speed advantage allows the Mars runner to overcome Earth's acceleration advantage.
A Note on Vertical Force
A number of sites around the internet seem to think runners go faster through vertical force. This is not really true. Because gravity is pulling the runners down, some vertical force is required to not fall over, but it's impossible to move forward only using vertical force.
Instead, runners are hitting the ground diagonally. Some of the force is used to propel them forward, and some is used to keep them upright. At low speeds, there's more power available (less is wasted moving their legs), and the vertical power requirement is constant, so more power is available for forward acceleration. At higher speeds, more power is required to keep their legs moving, so a greater portion of the power remaining is required to keep them upright. At top speed, they're just maintaining speed, so there's only a small amount of forward power being used to overcome air resistance.
We can see this in the angle of the runner's bodies. Off the line, runners are leaned way forward to balance against the intense acceleration. At top speed, runners are nearly vertical because there's no acceleration. But top speed is a result of how fast the runners can cycle their legs while staying upright, which is a result of how much power is left over after vertical power is taken into account.
If nerve cycling limits are in effect, the guy with longer legs wins, because each stride carries him farther and power stops being the deciding factor at all.
And you can't go faster by just jumping higher. Jumping higher means more time letting air resistance slow you down. The fastest sprinters will be airborne just long enough for the next step to be ready. Airborne less time means you trip and fall (or waste energy preventing said trip and fall). Airborne more time means more time you're not actively pushing forward to maintain speed.
On Mars, you'll waste less power staying airborne, so you'll have more power to propel yourself forward. But you'll still spend a bunch of power just cycling your legs at top speed, so the slight difference in air resistance won't make too much difference.
A Note on Human Legs
The above assumes runners on Mars would use the same motion as running on Earth. However, Mars' lower gravity means it will be optimal to lean forward more, which means the leg may not be at its optimal angle for transfer of power. I don't pretend to know how this affects things, but I suspect the answer is "not much". Once at top speed, the runner will be mostly vertical in either case.
References
This article, referenced in another answer by Anders Sandberg, shows experimentally what I've suggested above. Runners in low gravity automatically reduce the vertical force used so they bounce as minimally as possible. This is another way of saying they'll stay airborne just long enough for the next stride to be ready.