"March on, join bravely, let us to't pell-mell
If not to heaven, then hand in hand to hell."
--Shakespeare, Richard III V.iii.

Pell-mell comes from the Middle French pêle-mêle, a compound word of uncertain composition. Mêle comes from the verb mesler meaning 'to mix', but pêle is a bit of a mystery; it may be simple reduplication, or it may come from pelle (shovel) or paele (pan). In any case, in both French and English it meant the same thing: all mixed up.

This usage remained common for many years -- from the late 1500s through the 1850s -- and along the way was used to mean 'confusion', especially when referring to large crowds, and often specifically to soldiers in battle; to mean 'indiscriminate jumbling together of people or things'; and to mean 'rushing heedlessly'.

Historically, many writers have confounded the words pell-mell and pall mall. Pall mall was a game popular in Georgian London, played with a ring and mallet. The London street now called Pall Mall connected at one end to a game field where pall mall was played (the court was misleadingly called an 'alley'), but there are frequent claims that the name comes not simply from the game, but because of the rushing chaos of the road, which contained a number of gentlemen's clubs (including The Rag, The Athenaeum, the Carlton Club, the Royal Automobile Club, the Traveler's Club, and many others), major business houses, and eventually, the war office. It is possible that this is true to some extent, but misleading; while the road was officially named Catherine Street, it was from the start referred to as Pall Mall. This means that the name precedes the clubs and business offices by a good century at least, but reports are that the street was in poor repair and in need of widening, so it may well have been a pell-mell journey.

We have a number of similar words meaning pretty much exactly the same thing as pell-mell: pelly melly, helter-skelter, topsy-turvy, higgledy-piggledy... but not willy-nilly, which means something completely different.