Greetings mon! Rastakhan brought quite the interesting card, Hakkar, the Soulflayer. Previously Control Paladin struggled to beat any OTK deck, as well it lacked a discernable win condition against long value decks, but that all changes with Hakkar. It has many applications that are quite powerful for a control deck in that you can practically always win a fatigue race, as well as beat some OTK/Combo decks, most notably Mecha'thun, Shudderwock, and the currently popular OTK Paladin if played correctly. And thankfully, thanks to Prince Liam you will not be taking any damage from the Corrupted Blood on top of getting free Legendaries. Now that's value!
Here's my guide for you all :)
Strengths and Weaknesses
As mentioned above the deck can beat Mech'athun, Shudderwock, and OTK Paladin. Can win the fatigue race, and keep up against some more board centric decks such as Evolve Frog Shaman, Rush Warrior, Heal Zoo/Discolock, and Odd Mage. Can beat just about any control deck.
Decks with lots of big minions most notably Even Warlock and Taunt/Big Beast Druid. Struggles to deal with the constant flow of big minions as this deck doesn't have any hard removal besides Equality, so you'll be hitting them with your weapons quite often (ouch)
Deathrattle decks. Sticky minions and especially in the case of Hunter is hard to remove completely and efficiently with Paladin.
Odd Paladin. Struggles to keep up with their constant refill of the board, needs a Wild Pyromancer to stick to beat this but if can't it's a difficult matchup.
Odd Rogue is as shaky matchup but otherwise winnable.
Mulligans Vs Matchups
Hunter: Wild Pyromancer, Consecration, Truesilver Champion, Plated Beetle, Corpsetaker. Try to win the board and survive through DK and Zul-jin so you can eventually win with Hakkar, but is not important for this matchup as it's difficult to get Hakkar on the board.
Mage: Equality, Wild Pyromancer, Plated Beetle, Loot Hoarder, Truesilver Champion, Corpestaker, Zilliax. Treat Mage like an aggro/midrange deck, they have early game that you need to keep up with but it's not too fast. Try to flood the board as much as you can when you have board control to force their big removal so you have a breather to play Hakkar afterwards.
Warrior: Loot Hoarder, Hakkar, Corpsetaker, Truesilver Champion, Zilliax, Countess Ashmore. Typically a slow deck that will go to fatigue means you feast upon them, as long as they don't have DMH.
Paladin: Wild Pyromancer, Consecration, Stonehill Defender, Righteous Protector, Plated Beetle, Loot Hoarder (In case of OTK Pally) Just try to get your early game against Odd and against OTK your Hakkar as soon as possible.
Rogue: Righteous Protector, Plated Beetle, Wild Pyromancer, Truesilver Champion, Corpsetaker, Zilliax, Stonehill Defender. Same as Pally just try to get your early game as well as your mid game stuff to try and get board control.
Priest: Truesilver Champion, Corpsetaker, Wild Pryomancer, Equality, Zilliax. I dunno what Priest is doing mostly now but just try to get your mid game and especially equality in case of some Inner Fire shenanigans. If it's a control deck you know the drill...Amara isn't going to save them this time.
Warlock: Righteous Protector, Wild Pyromancer, Equality, Consecration, Plated Beetle, Truesilver Champion, Corpsetaker. Equality is a must in either situation for clearing Zoo boards and Even lock's big minions, and keep in mind save one equality and AoE for DK.
Shaman: Wild Pyromancer, Consecration, Equality, Plated Beetle, Truesilver Champion, Righteous Protector, Stonehill Defender, Loot Hoarder. Against Evolve or any kind of flood deck Just try to clear their board efficiently and you'll succeed. Against Shudderwock get to Hakkar as soon as possible and hope they don't hex your Hakkar, try to bait them out first.
Druid: Loot Hoarder, Hakkar, Countess Ashmore, Corpsetaker, Equality, Consecration, Wild Pyromancer. Hakkar is crucial to get down as fast possible, deters the druid to draw a lot and beating Mecha'thun. Token Druid can be a scary matchup so mulligan for Consec + Pyro as well as Equality for the Big minion decks. KEEP IN MIND try to avoid Hero Power as much to play around Spreading Plague and Gonk the Raptor, the latter is a potential OTK deck and having too many minions it can kill with the Hero power will result in your death. Better safe than sorry.
Reasons for changes: I feel this deck cannot afford to pull Wild Pyromancer most of the time, better to feel safe than sorry but CTA is still a decent option. Countess Ashmore provides much needed card draw and the cards you get help with surviving on top of a chance to tutor for Hakkar. There wasn't much Silence and Geist going around so I cut Undatakah, though it remains a decent option in the deck if the meta starts including them more. Sunkeeper Tarim is just good..much needed help against Even Warlock and other Big minion decks.
If you have any suggestions for changes to the deck, guide, or questions feel free to let me know.
Good luck and have fun!