The easiest solution is simply to define

unionAll = nub . mergeAll
where
-- specialized definition of nub
nub = map head . groupBy (==)

Talking about the easiest solution, I guess this is a quite easy way of defining unionAll as well: http://gist.github.com/306782
I, of course, do not claim that it is more efficient or better. But I don't think it'd be rubbish :)

--
Ozgur Akgun