Malthael certainly hasn't seen the same rush of popularity as Genji. I think this is partly due to his more niche place in Blizzards intellectual properties. However, this is also likely due to the fact that his play style is certainly very niche. I think to truly excel he is best picked in Draft where, like Tychus, he can be taken to counter bruiser heavy or high health teams. He's much easier to shut down than genji or D.Va as well as he lacks the mobility and control mechanics that both previous hero releases bring to the table. Come to think of it was Cassia released in between the two?
Regardless Malthael is certainly an interesting pick. I've definitely had a lot of fun with his kit and play style in the limited games I've played with him so far. I actually don't think he needs a nerf or balance change. He has low mobility and while his damage can seem quite high at times, especially with the level 10 power spike of Last Rites, his kit is so focused that he won't excel unless he is doing what his kit is designed to do: kill high health heroes.
Maybe your mileage has varied? I'd love to chat more about this!
I actually think he has decent mobility if you can keep up his Reaper's mark. You can constantly W and move around the map. That is also his weakness. Failure to maintain that mark will cost you not only damage but mobility and healing. I've had fun with him so far. I think he needs a damage adjustment. Not a major adjustment either. I think his place is in Draft, whether it be ranked or unranked. He seems to be detrimental in QM unless the person who is controlling him knows his mechanics.