[1] Beginning in the early twelfth century, leading notables in Kathmandu valley began to appear with names ending in the term Malla, (literally wrestler in Sanskrit), indicating a person of great strength and power.
Aridev was a great admirer of wrestling and was a wrestler himself, thus it is possible that he added the word Malla to his name and then the Malla dynasty came into existence.
[1] He was the first king to be called so, and the practice of adopting such a name was followed regularly by rulers in Nepal until the eighteenth century.
[2] Another possibility is that Aridev adopted the title Malla because it was popular at the time in India.
It seems more convincing because Aridev belonged to the dynasty started by Vamadeva, and that none of his predecessors used Malla in their names.