The practice of name-changing upon conversion to Islam was common from the time of the initial Islamic conquests through the present day. For the earliest evidence of this practice, we don’t have a ton of evidence, but I would recommend Richard Bulliet's Conversion to Islam in the Medieval Period. In this book, he utilizes biographical dictionaries - works that trace a person's lineage back several generations - to show conversion to Islam based upon when when "traditional" (a.k.a. non-Muslim) names turned into conventional Muslim names. The decision to change a name can vary depending on the individual, but it is often based on the desire to have an Arabic-language name as a way of establishing a deeper connection to God or the Muslim community.

However, changing names upon conversion wasn’t a universal practice. Seljuq Turks, Persians, and other peoples converted to Islam but rulers sometimes kept their ancestral names. I specialize in the Crusades, so Muslim rulers like Kilij Arslan, Kerbogha, Ridwan, and Duqaq come up. All were Muslim but none of their names are what we would today call typical Muslim names. I’m afraid I don’t know the frequency of this, though, nor how non-elites would have responded. Fred Donner’s Muhammad and the Believers talks about this topic as well.