It's the duty of the DM to make up random stuff.
On this particular instance, however, I want to say a thing or two.
Detect evil is not supposed to replace a paladin's judgement. A paladin slaying people left and right just because they blipped on his radar will have trouble with human justice -- and with his deity, too.
Eventually, he should figure out something is wrong, when he sees that Saint Lirna, the selfless holy woman who cures the ailments of the poor who can't afford even mundane medicine, registers as evil on his radar; while the Ratman High Priest who just sacrificed, before his eyes, a dozen toddlers and a virgin to the Crokzul the Ravenous, dark god of despair, suffering, hatred and self-destructive consumption, in order to summon forth a horde of undead and demons doesn't.
Especially given that the undead and demons don't register as evil either. But all his fellow paladins, including his master, his brother, whatever, do.