so the simple O(1) split would produce three submaps, the middle one having only one element. This operation would not be very parallelization-friendly.
Actually, I'm perfectly happy with that in this case!
A decent work-stealing system can tolerate a fairly large number of excessively small, trivial computations. It's having only those that's a big problem. (Which is what you often get if your parallel container ops spawn a task per element.)
Since Maps support O(1) size, the consumer of the split-up-map could choose to sequentially execute the singleton maps if desired.
Personally, I'm most interested in set-like operations and don't need any order guarantees. But that's another dimension in which one could chop up the API...
Maybe this does deserve its own module in the namespace, and maybe its own package, as Edward suggested.