So luckily I pulled Mecha'thun from one of my free Boomsday packs and I decided to try my hand at Mecha'thun OTK.
The deck also features a demon package consisting of Voidlordx2, Felsoul Inquisitor x2, Vulgar Homunculus x2, and Void Analystx2, Sense Demons, Skull of the Man'ari, and Bloodreaver Gul'dan. It's important to note that the OTK cannot be performed if you have a Voidlord present on your board as its deathrattle will trigger after Mecha'thun's, leaving you with 3 Void Walkers on your board and a very much alive opponent who will probably be laughing at you.
Finally the rest of the deck is filled with removal and draw.
Mulligan for Kobold Librarian, Corpsetaker, and Lesser Amethyst Spellstone. If you suspect your opponent is playing a slow deck, it's also a good idea to keep Skull of the Man'ari. Against aggro decks, keep Vicious Scalehide