Basil II received the sobriquet "Bulgar-slayer" quite frankly in recognition of the devastation his armies imposed on the Bulgarians during his lengthy efforts at reconstituting lost parts of the Byzantine Empire.
In 986, Basil II invaded Bulgaria and laid seige to the capital. The military campaign proving too costly, in blood and treasure, he retreated. In the year 1000, he tried again. Again, the war turned into a stalemate. In 1014, Basil tried again to conquer Bulgaria. The brutality of this latest, and ultimately successful, campaign earned him the infamy from which came the "Bulgar-slayer" moniker. The reason for the long delay between the military campaign and the conjuring of the moniker is simply a matter of chance. More than a century later, the nickname appeared in a poem. With the passing of time, legends grow and contort. Somebody referred to Basil II as "Bulgar-slayer," and it stuck.