I haven't seen a paladin in action yet, but I will this Friday. The Fighter in our group so far has literally controlled the battlefield with his marks.
The main benefit of a fighter's mark comes from his Combat Superiority, more specifically the ability to stop the movement of opponents with his opportunity attacks. The 3rd level fighter in our group took Sweeping Blow at level 3 and barreled into the fray, hitting and marking 5 foes and effectively blocking the corridor. On that round, even an attempt to shift by those enemies provoked attacks from him, and they didn't get to shift if he hit. Enemies that had not been marked faced similar consequences, their movement halted as soon as he took a swing. Sure, they can double move, but that's all they're doing on their turn.
A paladin in a similar situation would have been able to mark one of these monsters, and if it had ignored him, it would have taken a little damage. This, I believe, is the main benefit of a fighter over a paladin as a tank. Fighters have the power to lock down the enemies around him so they can't cause damage to his allies, at least not this turn.