As zebano says, Malz isn't that great.
He's a GREAT pub stomper, no doubt about that. But against skilled opponents he's not all that. Also level 6 doesn't give him an auto kill either in mid. You need to have malefic visions, puddle, ignite AND ult going to finish someone. That and you have to have the person dumb enough to stick around for that and NOT be a instant killer first either. For example, if I'm playing Warwick mid, you are dead as a Malz. You have ZERO chance of reaching level 6 before a Warwick. You can't push Warwick out of lane early and he can sit there and Q you over and over forcing any malz to go back to base to heal or die early. Same thing with an Akali. Kassidin can also own Malz. Sion too. Sion Pops shield, rushing in to stun, and backs out over and over. Constant harassment that Malz can't deal with. Why? Malz has ZERO sustainability. Right now the AP mids that have escapes or massive sustainability are the ones you want solo lane. They are the dominate ones. the other champs are going to suffer pre-level 6 in 1v1 match ups.
Here's what people don't understand, for 1v1 solo lanes you want champs with these characteristics.
1) Sustain. As a solo champ no one is coming to help. If a champ can't recover health and/or mana on their own they are screwed if the other person can out harass them. You want to be able to stay in lane as long as possible. The longer you stay in lane the faster you level up.
2) Survivability/Escape mechanisms. Not only does a solo lane have to contend with their enemy counterpart, they also have to be ready to deal with potential ganks against them. A good solo lane character has some way to deal with ganks and enemy harassment.
3) Ability to harass. Without having the ability to harass the enemy counterpart in lane, then you are just letting them free farm and harass you back. You aren't giving the other player any reason to leave lane to heal so you can get up in life. Nor are you allowing an opportunity to allow your jungle to come over for an easier potential gank that will result in a kill on the other enemy champ
4) Reliable CC for when your ganker comes over you can make sure you guys get the kill.
5) Last but not least Farming ability. You want a champ that can farm and push a wave if needed. Then roam around to help other lanes make kills. However, the other 4 characteristics are much more important first, but this is still is not to be ignored.
That is just for LANING phase. The list above has NOTHING to do with team fights in mid to late game.
So let us see how well Malz matches up to that list? Does Malz have sustain? Nope. Does he have surviability or escape abilities? Nope. Does he have the ability to harass? Yes. Does he have reliable CC? Not until level 6. Can he push a wave fast? Yes and no due to the random nature of malefic visions. So he has 2 out of 5 but only the least 2 of the 5.
Now here is my list of solo lane champs that are better picks based on early laning phase. These are in no particular order.
1) Tryndamere. Massive sustain. Escape with spin. Ability to harass with impunity due to sustain and spin. Fairly reliable CC with mocking shout. Can mow through waves with high crits.
2) Gangplank. Massive sustain. Escape with Fruit. Ability to harass with parley. Reliable CC with his passive and again later with ult. Can clear a wave with ult, but really needs madreds to eat through waves or high crit items so early game wave clearing isn't great but it gets much better.
3) Xerath. Not much sustain with health, but he's a special case that doesn't need it really. Why? Well... He has escape with stuns and toggle on/off foci for speed. Has a reliable CC. Has survivability with MASSIVE range. Has massive harass potential from massive range and stuns. Can clear waves easily. His range gives him the survivability he needs to stay away from potential ganks, poke his enemy counterpart, and free farm. While he lacks sustain he doesn't need it if played smart.
4) Morgana. Great sustain due to passive. Reliable CC with dark binding. Survivability with Shield. Can clear waves with soil easy.
5) Sion. No real sustain until level 6 with ult, but can be made up for with initial items easy. Very reliable CC. Great survivability with shield. Great harass combo with ranged targeted stun + shield. Can blow up minions waves like they are nothing.
6) Wukong. No real sustain without an item. Reliable CC after level 6. Great survivability with decoy. Massive harass (almost the best in the game) with nimbus strike + crushing blow + decoy combo. Can clear minions waves with nimbus pretty decently.
7) Warwick. SUPER Massive Sustain. Escape with speed if someone nearby is less than half health (which is fairly easy to do if you've been harassing with Q in lane. Ability to harass with impunity with Q. Reliable CC after level 6 though. Like GP though needs madreds to clear waves though.
8) Xin Zhao. Great sustain. Okay escape with charge if minion is there to charge back towards. Can harass with charge and knockup easy. Massive early game damage with three talon strike. Fairly reliable CC with a slow from charge and knock up from 3 talon strike.
9) Renekton. Great sustain. Reliable CC. Harassment and escape. This guy is a great solo laner. He is just lacking a good ult for team fights. For a melee AD his damage is a bit on the low side as well, but nothing that can't be fixed with items.
10) Alistar. Sustain with self heals. Harass with headbutt. Can clear waves with passive and pulverize. Reliable CC. Great survivability especially with his ult.
11) Brand. No real sustain without items but like Xerath makes up for that with great range. He has a large range with both pillar and conflag. Especially as a comb. Can clear waves easily. Has reliable CC with his Q if the player can land skill shots.
12) Anivia. No sustain, but with egg has great survivability. Built in slows in attack allow her to kite. Wall also gives her a great way to survive ganks. Massive early game damage. Reliable stun if the player can land skill shots. Can clear minions waves past level 6 like crazy.
13) Veigar. No sustain but has good survivability with stun ring. Which the stun ring gives him reliable CC. Can clear waves with ease. Can harass with stun ring and dropping his bomb easy enough.
14) Leblanc. Massive harass with dash + range + dash back. Reliable CC if one can land skill shots. Great escape with dash, chained slow, and passive. No sustain though. Can clear waves easily.
15) Caitlyn. Massive range harass. No sustain without items. Great escape/survivability with net drop and traps. Great early game damage if timing headshots early. Can clear waves with piltsover.
16) Miss Fortune. Massive range with double up. Awesome harass with double up. No sustain without items. Reliable slow CC with make it rain. Great escape/survivability with make it rain and passive speed boost. Can stop the sustain of enemy champs
17) Garen. Massive sustain with passive. Massive harass with speed + shield. Massive early damage. Can clear waves. Can escape with speed + spin to remove slows and being pretty tanky early on with courage. Will make an easy kill at level 6 if anyone is nearby with less than half health.
Now the guys listed above are great per level 6 and even better once they hit level 6. They are hard to push out of lanes for a varity of reasons, most of which I listed or are self evident, and can force their counter parts out of the lane.
However, not all on that list above are great for ever team comp. Some fall off in potential as the game goes longer. Some have lousy mid games with awesome late games. Some have the reverse. However, ALL of them have good early games in a solo lane and will flat out DOMINATE champs like Malz pre-level 6 in lane. I'd take any of those 16 champs I posted above against ANY Malzahar player no matter how good that player is and beat them to a pulp pre-level 6. Same with an Annie.
Now when it comes to mid/late game and team comps, some of the champs I listed above are flat out better than Malz there as well. Malz is a gimmicky one trick pony that makes for a great pub stomper. There is no doubting that. Like teemo. But no serious player is going to pick the champ in high elo to win games with the champ. He's is easily countered and dominated early game. His mid game can be great if he can get a bunch of solo kills with his ult. But his late game can fall off to shit. His ult is easily countered late game and has low range which puts malz into danger. Not to mention his ult is easily telegraphed. His Malefic Visions damage and passive pet damage is just to random to be reliable. His silence is easily dodged. And his puddle can be avoided unless used in conjuction with a hard CC.
Basically to reiterate, Malz isn't that good really. I've seen him do well, but there are other champs that can do what he can and do it better.