Contrary to popular perception, “Abdul” is not a word or name in Arabic. In Arabic, “Abdul” is completely nonsensical.
Now, there is a word (عبد; ‛abd; “servant” or, more precisely, “slave”). This is a very common element in Muslim names, where one would use “‛abd” paired with one of the Islamic names of God, if not “God” itself. The most common of such names is (عبدالله; ‛abdullāh; slave of Allāh/God).
Now, a little explanation on how such names are formed so as to explain where “Abdul” comes from and why it is wrong (in the opposite order).
In the nominative definite, (عبد; ‛abd) becomes (العبد; al-‛abdu). Let us take one of the Islamic names of God: (الملك; al-maliku; “the king” or “the sovereign”). When the two are combined using the (إضافة; iDāfah; possessive by juxtaposition) rule of Arabic grammar, the first word, although still definite (reflected in the retention of its nominative definite vowel ending) loses the definite article-prefix (ال; al). And so (العبد; al-‛abdu) becomes (عبد; ‛abdu).
Now, according to the rules of the same grammar rule/procedure, the last word retains the article. But following the rules of pronunciation of the definite article, the beginning vowel is suppressed and is replaced by the ending vowel of the preceding word. (Also, all words after the first are put into the genitive case – so al-maliku becomes al-maliki.) So: (عبد; ‛abdu) plus (ألملك; al-maliki) becomes (عبد; ‛abdu) plus (الملك; -l-maliki) which results in (عبدالملك; ‛abdu-l-malik). (At the end of a phrase or sentence, the ending vowel of the very last word is ignored, hence why “‛abdu-l-malik” rather than “‛abdu-l-maliki” and why “‛abdu-llāh” rather than “‛abdu-llāhi”.)
These names comprise of two components. To an ear unfamiliar with Arabic, the first component ends with the article, which makes sense as technically the first word ends with a vowel and the second starts with a consonant followed by a consonant and a vowel in an impossible combination (lsa, lHa, lka, and so on). And this is the origin, I believe, of “Abdul”.
This is not difficult to see in countries like Pakistan, for example, where names are rendered into English as “Abdul Rahman”, “Abdul Raheem”, “Abdul Razzaq” — and I choose these three examples to demonstrate that not only is the article tacked onto the wrong word but it is rendered incorrectly: before certain consonants (known as the “sun letters”), the l of the article is suppressed while the following consonant is doubled. (And so in such constructions as we are considering, the entire article is suppressed, the only vestige of its existence being the doubling of the initial consonant of the word to which it is attached.) Indeed, one may ask: how else is one to render such a name into English? For such a construction, there probably is no easy, universally-easy way.
And so we’re stuck with “Abdul”. Poor guy.
Now, regarding the name “Abdullah”, some wonder “How could Muhammad’s father have such a name before the advent of Islam?” The answer is simple: the pagan Arabs worshiped Allāh. For the pagan Arabs, Allāh was the supreme deity, the father of the gods and goddesses and spirits and whatnot. Muhammad’s innovation was not the introduction of Allāh. (عبدالله; ‛abdullāh) was a common name back then along with various other similar constructions with other deities: some examples are (عبداللت; ‛abdu-l-lāt), (عبدالعزى; ‛abdu-l-‛uzzā), and (عبد منوة; ‛abdu manāh). Muhammad’s innovation was that Allāh was the only deity that existed.