The Baghdad Mayhem mode is unlocked after completing the Baghdad portion of the game, which comes to a conclusion at mission 7. The mission has a number of waves that you have to beat, with each wave spawning more enemies and a generator that you must destroy within the time limit to reach the next wave. Enemies don't despawn between waves, and you can end a wave with all of the enemies still spawned, however clearing the map as much as possible is generally a good idea. Rinse and repeat the generator destruction process for 10 waves and you win.
To do this easily, I started off with a tank and bought a shield>tank>crawler>supply truck in that order, then upgraded the supply truck three times and upgraded the shields once each and continued upgrading everything else from there. Made the whole thing a joke with no losses and tons of excess abilities (30-40 repairs, for example).
Note: At this point you will not have all vehicles unlocked, so finishing up the campaign prior to doing this on higher difficulties would be a good idea.