Sheogorath before Shivering Isles is conflicted, with one Chaotic Neutral and one Lawful Neutral side, both fighting for control. Afterwards it's easier to class him as CN because he's freed of the LN influence.

Malacath I'd stick into NE rather than LE, or CN. The only code he follows is his own code, and he adheres to it regardless of outside influences. So he's neutral because he's not doing things Chaotically, but he's not obeying your Laws either.

As for evil, certainly. He's after power, for himself, for his worshippers, and he's not afraid to use any means at his disposal to get it. If it costs him a few followers to get it, so what, there are always more. After all, he has reserves.