There's the tradition: "Blessed is the house wherein dwells a Mohammed." So lots of boys got named some version of Mohammed.

Traditional Arabic names don't have modern European "first, middle, or last name." They have a personal name, a given name. They don't have a fixed inherited family name (that's so 20th century).

All those other names you see are either eke-names or patronymics, or both.

An eke-name ekes out your lone personal name. In many cases, anyone who comes from another place gets an eke-name based on his old residence. So in Morocco, say, you would have Mohammed al-Baghdadi and Mohammed al-Ymeni, who came from Baghdad and Yemen. There are also eke-names that refer to qualities of Allah, like al-Malik, the King, or ar-Rahman, the All-Merciful.

Then come the patronymics. Did you see the scene in The 13th Warrior where ibn Fadhlan lists off that whole string of names? Those are all patronymics (or patronyms) listing his genealogy to identify himself. "Ibn" isn't a name: it means "son of." So you get Achmed ibn Fadhlan ibn al-Baghdadi, which would be Achmed, son of Fadhlan, son of al-Baghdadi. You will see a lot of classical authors known by their patronym: ibn Fadhlan, ibn Battuta. The "daughter of" word is "bint."

In modern times, some people took family names required by the law that included a variant on Mohammed.

Even at its worst, it's just a parallel to times in the Middle Ages when every fifth Englishman was John.

Source: Ingraham, People's Names