If you have access to the DMG (if you're DMing, you're going to want it) page 57 has a chart listing how much XP an encounter of level X for a group of 4, 5, or 6 PCs should be. You ought to be able to modify this for a group of 2 fairly easily by taking the XP for a 4-person encounter of the level you want and dividing by 2.

In case you don't have it handy, here are the XP totals for a group of 2 for the first 10 encounter levels:

1. 200xp
2. 250xp
3. 300xp
4. 350xp
5. 400xp
6. 500xp
7. 600xp
8. 700xp
9. 800xp
10. 1000xp

Remember that not every fight should be the same level as the party. Fights of the party's level are average difficulty (or easy if the party is optimized), fights of lower than the party's level are easy (or speedbumps at best if the party is optimized), and fights that are higher than the party's level are hard (how hard again depends on party optimization). Generally any fight of less than party level -2 or -3 is too easy, and any fight of party level +4 or more is too hard for all but heavily optimized parties. The same range also applies when selecting monster levels, so monsters should be within 3 levels of the party; a single regular level 10 monster might be the right amount of XP for a level 1 encounter (in a 5-person party), but its defenses and attack values will be much higher than the party's.

Thus, if you want a typical fight for a level 1 party with 2 PCs, you should use 200xp worth of monsters. If you want a challenging fight for a level 1 party with 2 PCs, you should use 300xp of monsters. You can compare a fight's XP total to the recommended XP for a 5 person to estimate what level the Kobold Hall fights should be, then turn it into an appropriate fight of the same level for a 2-person fight.

That said, paladin and warlord is a relatively good 2-person combination (as long as the paladin has a good MBA), so you might find that you need to add in a little extra XP worth of monsters. If you find that adding monsters makes combat take too long (paladin & warlord combo has a lot of healing, but isn't a damage powerhouse), try going back to the normal number of monsters, but double their damage and cut their HP in half.

(For what it's worth, I think a party of 5th level adventurers could mop the floor with a single CR9 monster)

From what I can tell, the crux of what you're trying to accomplish here is to have a monster with a very high effective defensive CR, while keeping the offensive CR reasonable. Such a monster will be able to last a long time against the party, but not be able to wipe them easily. But as you can tell, simply jacking up the monster's HP makes for a slog.

Split the fight into multiple encounters/stages

This tactic is a classic trick in video game RPGs: after dealing a certain amount of damage, you change the boss's form or the circumstances of the fight. This allows you to mix up the fight, and effectively turns the fight into multiple consecutive encounters hidden within a single battle.

For example, a party I play in recently fought a homebrewed boss dragon. It started with some chromatic abilities, but after we dealt enough damage to it, it changed into a dragon with all of the chromatic abilities. After that form was defeated, it turned into a shadow dragon. Afterward, the DM said that he just chose a CR-appropriate dragon, and then added not-so-powerful abilities to it for each stage. The resulting fight was both long and difficult, but not too difficult.

In my own game, I have used a boss that starts in a human form, then turns into a dragon form, then into a more powerful dragon form. Alternatively, you could have the boss retreat to a different location--perhaps one where he has traps set up or some terrain-based advantage.

One nice trick is that you can use the form change to clear otherwise debilitating effects. Almost every single-monster fight ends up being lopsided because of the imbalance in the action economy, but having your monster change forms gives you an excuse to get rid of that debilitating status effect (stun? sleep?) or allow it to survive a massive nova (a paladin dropping a ton of smites in one round of attacks, for example). At the same time, it doesn't render the players' actions completely useless, because they still made that stage of the fight easier.

Give the monster an interesting defense

If you don't want to have changing forms, you could try giving your monster interesting ways of keeping itself alive.

For example, consider the Archmage (MM 342). While he technically has access to 9th level spells, none of them directly deal damage. In fact, his highest level damage-dealing spell is the 5th level cone of cold, and all of his spells of 6th level or higher are defensive. Thus, he has a great deal of potential survivability, without being able to wipe the party in one shot (which he could easily do if he had meteor swarm instead of time stop). In my game, I had a fight where an archmage could form a huge slime armor around himself, which gave him extra tentacle attacks and a shield the players had to bypass first. Thus, while boss's damage output wasn't too high, it became an interesting puzzle for the players to pierce his defenses.

In the end, the PCs are always going to be super death-dealing machines. In order to have an extended, meaningful fight, you have to find some way to make their damage output materially useful during the fight and have some way for the boss to survive that damage output. The fastest way to a boring fight is for the players to feel like their attacks aren't making a difference, until the boss suddenly drops dead.