His weakness, imo, are people with quick gap closers, and CC such as silence or stun. Needless to say, LB and talon are two good candidates that come to mind, specifically LB since she can get in, burst, silence, and get out more reliably.
Also, know the build. AD malz will rely less on spells, and more on voidlings (*******s hit over 270 with about 1.5 attack speed), and thus you need to take the minions out from ranged (getting close to him lets him auto attack and spell spam more minions out). Note that even when Suppressed or stunned, he is still a threat if even a single voidling is out.
AP malz will have much higher burst, though generally be squishier. the voidlings wont be a big deal, more or less free gold. However, a malefic visions bouncing on you, or a neather grasp will hurt on its own much more. His big weakness is spell CD's.