It was created by orientalist writers like Lovecraft as an "exotic" name and subsequently popularized in the Anglo literatisphere as a stock Arab character name. doesn't really exist in the Arabic-speaking world as an independent name, even if it's become common in western countries.
It comes from the word "abd" (عبد) in Arabic, which means servant or slave, combined with "ul" or "al" (ال), Arabic's only definitive article. "Al" can also express possession. It's often used as part of theonyms like Abdallah, meaning literally "servant of God," or like Kareem Abd-ul-Jabbar's name which means "servant of the mighty."
This post brought to you by a high person taking a week off work
My guess is it's anglicization and they just chose to stick with it. A lot of European immigrants did the same thing with their names where some Anglo heard what they said and wrote something similar down.