Well just brewed this up for the Tavern Brawl, tried it out, went pretty well 10 wins.
Well for now my mulligan is fairly simple:
You want Underbelly Angler (or both)
You want Murloc Tidecaller (but only one, mulligan the second copy)
The rest just hard mulligan for the Underbellies... If you do have Underbelly then keep all the cheap murlocs (1-2 mana cost) except the Echo ones, they are not considered to be cheap they are supposed to be mid game refills instead.
If you are on coin then unless you have Tidecaller consider coining out Underbelly, because it is just that good if you get value out of it... Well Unless you opponent played Flame Imp or something else that can kill underbelly.
Also there is interesting consideration with playing of Murloc Tastyfin if you expect your board to be cleared then definitely spend 4 mana to drop him so that at least you get hand refill. I even played it into Doomsayer just because I care about it's deathrattle that much.
Don't forget to totem up if you are running out of steam. Bloodlust can be a good finisher if your opponent SMOrcs...
Soul of Murlocs just play it when you have mana to spare with 3+ minions on board or expect a board clear.
And here is my first run. I might do more runs in brawliseum this week. (loses are marked)
https://hsreplay.net/replay/G9hGJvp3pgRMQBuQHcc5Sh - vs some hunter
https://hsreplay.net/replay/kapsnG22H54QDu6zJm6dAk - first loss to dragon paladin... drew really badly and ran out of steam.
https://hsreplay.net/replay/aYoAx8KLycNSD8GN5cZxFi - vs Thief rogue, got so much value out of Underbelly Angler that rogue just gave up turn 3.
https://hsreplay.net/replay/8i5os7ihEbqNxPi4JJ7iub - vs Zoolock
https://hsreplay.net/replay/zkUg5UJ6Td7RQYiPdB5y9C - mirror match.
https://hsreplay.net/replay/ofGxZcgqnbEturYiKFyNdK - some vereesa hunter
https://hsreplay.net/replay/25LS9tmUEkzekkZLBsG4VJ - some warlock. I would assume control but I killed him turn 4 he only played a single Spellbreaker before dying...
https://hsreplay.net/replay/PX4CbjNLT7d8vDzAG9GRrk - second loss to control bomb warrior. But I suppose that is my counter, but even then I can sometimes highroll as you will see later.
https://hsreplay.net/replay/ZeRYy5RteYUHXnRZyKztH6 - dragon warrior... managed to do value train on turn 9 against him...
https://hsreplay.net/replay/8hZzFFKgVsjTorjfRvHgRD - vs summoner mage
https://hsreplay.net/replay/ToqQkFRg23FRWTmgdgudw6 - another bomb control warrior, but he didn't clear my totem, and this game shows why I have bloodlust in my deck... surprise lethals with your totems are always nice...
https://hsreplay.net/replay/S96fFhEy6KEYbtmDWD4dER - vs some mage with stuff triggering of small spells...
https://hsreplay.net/replay/6kX2ZLHfGB6zPniv4Xfiaa - third loss, well yeah control warriors aren't easy to beat still... possible but not easy.