It seems like the *on family in general has a nontrivial increase in space usage and the only differences have to do with application specific time vs memory tradeoffs that need to measured at the application level.
To be clear, this particular tradeoff isn't relevant for every *On function. Of the ones under discussion, it applies to sortWith, groupAllWith and groupAllWith1, but not groupWith or groupWith1.
Some things I think are worth noting:
* There must be lots of common functions that could choose different implementation tradeoffs, but we don't keep multiple versions of them around.
* The existing performance differences aren't documented. (Data.List.sortOn tells us that it only evaluates `f` once per element, but it doesn't tell us about the costs; the others don't mention performance at all.) I predict very few people currently choose between GHC.Exts.sortWith and Data.List.sortOn according to their performance needs.
* The Data.List.sortOn implementation is somewhat subtle and complicated. The NonEmpty.sortWith implementation is literally `sortBy . comparing` and GHC.Exts.sortWith isn't much more complicated. (`sortWith f = sortBy (\x y -> compare (f x) (f y))`; I don't know if there are reasons to prefer or disprefer this compared to `sortBy . comparing`.) If someone wants this behavior, it's not hard for them to get.
Based on these, I don't think there's much value in deliberately[1] making sure both implementations have a name, which is why I proposed to replace `sortWith` with `sortOn` instead of keeping them both around.
[1] Of course, there's value in not changing things once they're there. By "deliberately", I mean that if we weren't already in this situation, and someone proposed adding a separate function that was semantically equivalent to `sortOn` but implemented as `sortBy . comparing`, I don't think that would see much support.