Hearthpwn

NOTE:

~31% of Wild Ladder is Reno Priest according to VS (and I believe it cos it resembles my stats) - if you are over Rank 5 I strongly advise to use 2x Divine Favor, kick out anything for it (Tirion recommended).

!!!  WARNING  !!!

Murloc Warleader will be nerfed on September 18th! The deck most likely won't be this broken after the nerf. I am not sure how much will it get hit, but I assume the deck will still be pretty good. Still I need to warn you! I wouldn't craft any epics or legendaries just yet! Wait couple of days after the nerf to see how the deck does before investing dust, make it only if you already have all cards!

NOTE:

This deck costs 13800 dust, however many of the cards, including 3 legendaries, can be easily replaced by almost as good commons and rares (if not even a bit better in certain circumstances) so just check "Replacements" section.
EDIT: Here is the "budget" variant of this deck that cost 6960 dust, literally half the cost of the original, changed Boom and Tirion for 2x Bonemare, Coghammer for 2nd Rallying Blade, etc. Overall pretty similar deck and not much worse at half the price, not as good but I'd say not more than 5% win rate difference on average (not tested to full tho, just an assumption):

Introduction

Hey guys,

Just reached Legend in Wild with ease using this deck so I wanted to share it. It destroys Druids which was one of the main goals for me, and Paladin is the last class to make golden which was another big reason, so I decided to go for it. I didn't track games but I assume I had around ~80% win rate (a bit less than 100 games total to Legend, know it by number of Paladin wins). 

Here is the proof:

I will write some mulligan guide and some tips soon, but it's very simple and similar to old Midrange/Murloc Paladin from Standard which I have the guide for if you care:

[S37 Legend] Midrange Paladin Guide

Gameplay

This is a tempo deck. It has sort of aggro-midrange curve and relies heavily on snowballing and board presence. Versus aggressive decks trade as much as you can and control the board heavily and versus slower decks you act like an aggressor. Do as many trades as possible vs aggro and don't play for value at all, literally kill his 1/1 with your 3/3 if needed. You will outvalue them by far for sure in time, you only want to survive vs them. Coghammer is usually a win card vs aggro - trades alone into 3 small minions and shields you. Versus slower decks be greedy, wait for 5/4 to buff couple of murlocs, wait for bunch of murlocs to be on board if possible with Old Murk-Eye, while you'd often just drop it as 2/4 to trade vs aggro. You get the point, it's fairly simple, play for tempo try to gain value, trade when favorable, play more aggressive vs slower decks making them do the trades for you, while defending at all costs vs aggro.

Card Choices

Overview of couple of choices that I see people are not running in their decks. I have checked quite a few decklists online and experimented myself with couple of variations. Other cards do not require any specific explanation in my opinion and if you have any questions just ask. 

• Coghammer - I didn't see this card played at all in Wild, which is a mystery to me. It is just too good, one of the best weapons in game that wins games alone vs aggro decks such as commonly seen Pirate Warrior and Aggro/Token Druid. It also makes Rallying Blade itself stronger since it's basically an additional divine shield. I use one of each weapon since if u don't use Coghammer, Rallying Blade becomes a bit worse and you don't have enough divine shield minions, yet if you'd use 2 Coghammers without Blade, you'd have too much divine shields so Coghammers effect might be wasted (if it casts on a minion that already has shield). 1 of each is a perfect balance imo. 
• Dr. Boom - Seen literally 0 Dr. Booms in my climb from R16 to Legend and I find it laughable, it's still one of the best cards in game, still better than any 7 or even 8 drops (only a couple of cards you might need for synergy might come close to Dr. 7). Card is broken, use it in every deck, it didn't change, it didn't become worse - it's still broken and the best choice for any deck that is not pure face click. It has insane tempo and adds a lot of pressure on the opponent. Also hard removals aren't run so much aside from Reno Priest, so opponent will pretty much always have to trade into Dr. Boom or he is dead. 
• Small-Time Recruits - Kept 2 Divine Favors at 1st but faced too many Pirate Warriors and Aggro/Token Druids where Favor does nothing, and Small-Time Recruits is consistent and can be cast at any time and due to so many 1 drops, it will always draw 3 cards. It can also be good to be cast before Finja, so Finja summons stronger murlocs.

Mulligan

Keep 1 and 2 mana cost murlocs vs everything, and you can keep Shielded Minibot vs everything except Priest (you want to lure out pain on something that doesn't have divine shield). Can keep 3 drop if you have first two turns. If you have 1-2 drops already, you can keep Divine Favor vs Priest and Warlocks, as they have like 8-10 cards very soon so it will draw half your deck which will lead you to easy win.

I will write this in more detail when I have time with specific cards and which 1 drop you should keep in which situation, but generally you can't go much wrong, as long as you are not keeping idk Tirion and Dr. Boom.

Replacements

If you have any questions and suggestions, please let me know so I can update the guide, for now here are some epics and legendaries you might not have:

• Tirion Fordring - Bonemare
• Dr. Boom - Bonemare
• Old Murk-Eye - Murloc Knight / Primalfin Lookout / Coldlight Seer / Wickerflame Burnbristle
• Small-Time Recruits - Divine Favor
• Coghammer - Rallying Blade

Standard 

For those who want to stick with Standard here is variation of it for Standard mode:

Good luck!