puppet with some other stuns should be a fine counter to magebane. He has both hold to disable his blink, and then puppet show and his ult to finish him off.
i think pest is pretty strong against him, especially around level 7.
arachna is a possible counter, just since she can slow him way down during teamfights, and her ult works through bkb.
silence him, disable him, throw alot of damage his way. If you let a carry farm, they are going to carry.