Well, the real question involved in any "deal with the devil" or "deal with the demon" type scenario is this: Why will the demon deal for anything that isn't evil?
The deal with a paladin analogy, while thought-provoking fails because, unlike demons, paladins have a lot of interests that aren't GOOD. For instance, a paladin might well want a fancy dinner to impress the head of his order when he comes visiting the paladin's chapterhouse or a good marriage for his sister (or ward) or a good dowry for his nephew. All of those are deals with a paladin but of a purely mundane nature. There are (or should be) no purely mundane deals with the devil. All of them should have a spiritual significance and price tag--it might not be obvious, but it should be there.
In this case, the spiritual price tag is not particularly subtle:
The Church of Nerull would guarantee the following:
1. They would remove all plague and disease from the city of PL in 4 weeks
2. They would lower the current mortality rate in PL to mimic AT
Both of these cede influence to Nerull and his cult. Why not make the head of the Nerullite temple the minister of education in the city while you're at it?
3. They would provide complete support to the military in the upcoming campaign (3 Clerics per company of troops plus 500 healing potions per month)
Exclusive chaplaincy for the Nerullites. Why not just appoint the Nerullite priests as the officers of the military here? You can bet that they're going to make "good" use of that influence.
In exchange, Mortimer would have to deed a specific plot of land in PL to the church of Nerulls use for 50 years. The plot of land would be used to build a church of Nerull. This specific plot of land covered 3 of the 4 churches in PL, and would cover the land currently held by the churches of Pelor, Heironeous, and Kord. The ony remaining church owning land in PL would be Nerull (massive plot of land), and a small chapel of St. Cuthbert.
In exchange? Oh, yeah, I guess Mortimer does see the first stipulations as benefitting him rather than the Nerullites. In exchange, he's going to raze the temples of Pelor, Heironeous, and Kord and erect a temple to Nerull on the same ground. Not very subtle there.
Pelor: What are you doing Mortimer?
Mortimer: Well, I'm tearing down your temple and destroying your altar and your idol.
Pelor: That's MY altar! How dare you destroy it?
Mortimer: Eminent domain, Pelor, old chap. I've got this contract to build a temple to Nerull so I'm sorry but I've got to claim your altar here. Interests of the state and all that.
Pelor: Nerull!?!
Mortimer: Yeah, Nerull. I don't know what you're getting so upset about. I mean, sure, he's your ancient enemy, the god of evil, death, unlife, and decay, but I'm getting a sweet deal on healing potions and a bunch of chaplains for my army. Besides, it's not like you're the only one I'm evicting. Kord and Heironeous are getting the boot as well.
Kord and Heironeous: What?!?
Mortimer: Yeah, Nerull needs a really big temple, since he's the god that's saving our city, we want to honor him more than any other god, so we're razing your temples to make way. No blasphemy intended, old friends. I mean, it's not like they'll be sacrificing more than one or two virgins a day on your sacred ground or digging up
all of your saints in the crypts below to animate them. I mean, I've set a strict limit on the number of sacrifices and I've given your priests 7 days notice to dig up and remove any corpses they don't want animated.
So is the deal evil? You bet.
Is Mortimer evil? Let me see, he's rejected Pelor, Heironeous, and Kord and made Nerull the de-facto state religion, planted throughout the entire fabric of the economic and military apparati of the state. Maybe the moral status of someone who does that depends upon how the DM judges weighs his intentions and his deeds. To that extent, it depends upon the moral culpability of fools.
Is Mortimer now an enemy of Pelor, Heironeous, and Kord? Without a doubt.
Is the latter more significant than the alignment? That only depends on whether those gods decide to respond with Flame Strike or Holy Word.