The sword’s power changes with time, and as it racks up more kills. Soon, it gains a +1 to attack and damage. Then, it can become wreathed in flame as a bonus action. Then, it grants advantage to checks made to locate creatures. Then, its base power inverts and it can only kill non-evil creatures.
Do not tell the player about that last one. Insist to the player that it works exactly as you first described. The Paladin can kill innocent shopkeepers and little old ladies, but cannot kill this assassin working for the BBEG.
Will he question his own stab-first ask-later methods? Or will he turn evil without even noticing?
See, here’s my problem with that: humanity is inherently evil so everyone would be killed by such a thing.
If humanity were inherently evil, we WOULD NOT BE HERE RIGHT NOW
Yet here we are, and evil we are. Case closed
You can go ahead and waste time beleaguering the point if you want. It’s not gonna change the fact that humanity is inherently evil whether you like it or not.
If it makes you feel better, it means I am evil too. Then again, so are you. We all are. It’s just the natural state of being human.