There are lots of counters to Malzahar's suppression. Before I continue I'll caveat that I think Malz needs a nerf (he's actually my first choice to ban right now), but the necessary nerf may not be his ultimate and his ultimate does not lack counterplay.
First, as an AD champion you can easily counter his ultimate with a single item
in to
. The active will end the suppression, problem gone.
This isn't always practical though. You don't want to rush QSS on ANYONE, let alone a mid laner. He'll obviously hit 6 before you get QSS as a second item, so what do you do?
Prioritize an item with some MR first.
AD:
is pretty much a standard start against any AP champion
AP:
is great, unless you need mana regen then go
> 
These items will let you survive his full combo engage. If you don't want to go for that early (I don't know why not, but perhaps you're trying to rush something yourself) there's always the option of running scaling MR glyphs (by 6+ they'll be close enough to flat and better shortly thereafter) and buying a second
for a bit more survivability.
For counterplay a little longer in to the game, Malzahar's ultimate is easily interrupted. Any CC will prevent his channel. Someone on your team should always have a CC available to interrupt his ultimate in a teamfight.
Most mid laners also gain their roaming power around level 6. Most should either be able to farm from a safe distance (he can't engage) or should be able to roam to snowball other lanes until it's time to teamfight (so allies can break the channel).
Malzahar's true strength lies in his easy laning via e, his aoe silence, and his voidlings. His ultimate is just a gimmick that catches most people off-guard, especially if a team blows all of their CC early in a fight.