Control.Exception is designed for use:

• in otherwise pure code where the addition of an error-related monad or other error reporting structure would be too cumbersome
• in cases where one thread or process needs to raise an asynchronous exception in another process, outside of the type system’s constraints.

For an example of the first, take division by 0 in the Int type (e.g. div 3 0). You can’t give a reasonable answer in that case, but you don’t want your divide operator to return a Maybe Int – it could make programmers miserable! So you could use an exception to stop the computation.

In this situation, you could also use error for a similar effect. The difference is that Control.Exception gives you more flexibility for catching and reporting what happened. But such exceptions can only be caught in the IO monad, which could place a burden on your client. Therefore, I’d suggest you save these for truly exceptional, perhaps catastrophic situations.

The stuff in Control.Monad.Error works via a monad, and uses the monadic binding/sequencing machinery to pass the error along. It doesn’t subvert the type system like throw does, so it has the virtues of purity and relative transparency going for it. It also gives you more flexibility to handle and recover from errors, and can also make it easier to pass errors back to the client if you’re writing a library (see Parsec and polyparse, which both transform some monadic error + result into an Either value when they’re done, though polyparse uses something a bit different from Control.Monad.Error). But of course you have to work within the error-handling monad, or wrap an error-handling monad transformer around whatever existing monads you might be working in. Both options can make your code considerably more complex.

If you haven’t already, see Real World Haskell, Chapter 19 for a rundown of these and other error-handling options, and see the end of Chapter 18 for some of the more general drawbacks of using monads and monad transformers.