Vesh, Plague Lord of Murlocs
It’s best you find out now, Vesh will NEVER run out of Murlocs. He has plenty of cards that resurrect Murlocs, multiple copies of Megafin, Tip the Scales, Mrgl Mrgl Nyah Nyah. Also the Chapter’s Twist: Twist - Plague of Murlocs , will consistently generate more at random. On principle, it’s best to clear away as many Murlocs as you can. However, in the later stages of the fight, it’s better to not expend all of your resources clearing away every single Murlocs. He’ll most likely be able to fill his board every single turn if you try to do that. Preserve your resources so that you have it when you truly need it.
Despite what was mentioned before, you have no choice but to clear all of his Murlocs. 34 Murlocs have to die in order to move onto the next stage. As long as you make good trades, you should be able to tough it out until the next stage.
Since he is Immune, he takes advantage of it by using more than one Fool's Bane as removal tools in addition to Plague of Murlocs. Be aware that he’ll usually play this on Turn 5 if you both have minions on the board. He’ll attack whatever you play, so you can toss out some extremely low-stat minions for him to use the durability on.
This is where you need to be strategic in your removal. Unlike in PvP games, Underbelly Angler isn’t really a priority target. He already has more than enough ways to generate tons of Murlocs, so letting it live isn’t a big deal. In addition to Murlocs, he’ll have Sea Giant to throw on the board for free most of the time. If you have any transform effects, save them for his strongest Murlocs instead of the giants to decrease the chances to him resurrecting it with his boss cards. He’ll typically use his hero power Ashes Anew as often as he can, even if it means sacrificing his own Murlocs.
Even though the Heroic version of this hero power allows him to kill your Murlocs as well, he’ll sometimes kill his own anyway even when you have one. He’ll generally favor killing his weakest Murloc over one of yours unless you have a notably strong one. For that reason, it’s unwise to heavily invest in just one of your Murlocs. Though at this point in the fight, having several Murlocs can be an asset. Since it’s extremely hard to clear away all of his Murlocs before killing the Scaly Golem, it’s just as good to have several Murlocs of your own to benefit for its Deathrattle as well.
Upon moving onto the next stage, Mur-nado will cost (10). If you have a big enough board, he will simply shuffle them all into his deck to get rid of them. He still prefers to summon tons of Murlocs as opposed to summoning stolen minions unless he gets some sort of extra benefit. The main issues when dealing with his hero power is trying to keep the board at a healthy balance on both sides. If your board it too big, he’ll just removal it all (usually for free). But if he also has rather powerful set of minions, he’ll avoid doing so. He’ll generally want to save it for when he has a HUGE minion disadvantage.
Also, thanks to the hero power, he is the only Plague Lord that will not lose to fatigue. So you’ll often have to attack him instead of his minions in order to bait him into trading instead of shuffling everything away. The way to do this varies wildly depending on the circumstance, so there’s no set formula for trying to manage Mur-nado. Although, the cost will increase by (1) with each use. So he won't be able to use it every single turn.
Hero Pre-Adventure Selections
Reno Jackson: There will be plenty of instances where you can easily get most if not all of Vesh's Murlocs down to 1 Health, allowing your hero power to most likely sweep a majority of the board. The Gatling Wand is a nice way to clear away an entire problem board that you otherwise can't deal with as well as remove a chunk of his Health.
Sir Finley: This package will definitely help with the regular damage you'll be taking throughout the fight. It will not only provide consistent healing, it can also be used to kill off problem minions like Murloc Warleader.
Elise Starseeker: At one point you'll probably need some form of healing to stay in the game with all the Murlocs you'll be enduring. Staff of Renewal can also act as an emergency wall when you're almost down and out. Note that each stage Vesh will have 2 copies of Plague of Murlocs. Be aware of whether or not he used them to make sure you get the full benefit of the treasure.
Brann Bronzebeard: Since the board will constantly be filled with Murlocs, Flo will net you a total of 2 treasures to match the persistent aggression. And since falling behind in tempo against a Murlocs deck can be devastating, having Dino Tracking can greatly reduce the the likelihood of getting dead draws.
Alchemist's Stone: This passive treasure is a fantastic way to keep up with the constant onslaught of Murlocs Vesh will continuously summon.
Band of Scarabs: Decreasing the Attack of all of Vesh’s Murlocs can really slow the aggression when he decides to rush you down. It can also cause him to use more Murlocs to break through your Taunt minions.
Titanic Ring/Staff of Ammunae: These treasures can block off an assault that would otherwise be too difficult to deal with. It’s especially useful for preventing Old Murk-Eye from instantly taking out a chunk of your Health in a single hit.
Recycling: This will help you stay alive way longer, as well as give the random Murlocs you summon a little bit of extra value.
Tracking Device/Map of Uldum: As a Murloc deck, not being able to deal with the early turns can definitely snowball into something you can't handle. These treasures can help you keep up with him in the early turns.
Ancient Reflections: This treasure can be extremely good, but you can’t use it on just anything. The true target for this spell is Old Murk-Eye. Assuming that Vesh has 7 Murlocs on the board, you’ll have 7 minions with 15 attack that all have charge. That’s enough to win you the game all by itself during the last stage of the fight.
Do Not Take
Phaoris' Blade: This can usually allow you to snowball into a very strong offensive power house. But Vesh has the more aggressive deck of the Plague Lords, so you’ll almost never have enough Health to tank enough hits to get Phaoris' Blade up to a meaningful value.
Crawling Claw/Reno's Crafty Lasso: Vesh has basically no cards that will cripple his gameplay if it gets stolen. It typically won’t give your own deck a massive boost either. Also, Megafin can easily just replace the stolen card with another Murlocs.