As per a long discussion on #scalaz this should at the least have the documentation of the haskell eg.

    -- | /O(n*log n)/.
    -- @'map' f s@ is the set obtained by applying @f@ to each element of @s@.
    --
    -- It's worth noting that the size of the result may be smaller if,
    -- for some @(x,y)@, @x \/= y && f x == f y@

or possibly something more formal such as:

    /* 
     * For the Functor composition law to hold it is important that the Order[B] is substitutive for the Order[A] – 
     * that it, that the Order[B] should be _no stronger_, it should not distinguish two B instances that would
     * be considered as equal A instances.
     * 
     * Note this is not able to implement Functor due to the Order constraint on the destination type,
     * however it still is a functor in the mathematical sense.
     */

I don't know if there is any way to witness this constraint in the type signature.