The doc string says “returns a new map”

Yes but intuitively I was expecting the new map to remain sorted

Not saying it definitely should but that was my expectation

From the implementation, looks like there was a preference to always achieving the performance of transients in update-vals, at the expense of returning a "vanilla map" if the input map does not implement transients, which several alternate kinds of maps do not.

Yep, there were tradeoffs and we made our choice there as reflected in the docstring

sorted-map isn't a clojure.lang.IEditableCollection?

No, as can be demonstrated quickly in a REPL:

Clojure 1.11.1
user=> (instance? clojure.lang.IEditableCollection {})
true
user=> (instance? clojure.lang.IEditableCollection (sorted-map))
false

It is of course possible to develop a modified version of the sorted-map implementation that implemented that interface. I do not know whether its performance advantages would be worth the development effort.