Yeah the Map monoid instance is very unfortunate :( When I came from Scala I really missed the one in scalaz (which is as you describe)

reducers has a UnionWith newtype which gives you the better Map monoid. But I think it uses a lazy unionWith, which will cause your Map to leak space when used in a foldMap over many elements :(