Q:

How to define an instance of Data. Foldable. Constrained? 

I've successfully defined Category, Functor, Semigroup, Monoid constrained.  Now I'm stuck with Data. Foldable. Constrained.  More precisely, I seem to have correctly defined the unconstrained functions fldl and fldMp, but I can't get them to be accepted as Foldable. Constrained instances. 
My definition attempt is inserted as a comment. 
{-# LANGUAGE OverloadedLists, GADTs, TypeFamilies, ConstraintKinds, 
FlexibleInstances, MultiParamTypeClasses, StandaloneDeriving, TypeApplications #-}

import Prelude ()

import Control. Category. Constrained. Prelude
import qualified Control. Category. Hask as Hask
-- import Data. Constraint. Trivial
import Data. Foldable. Constrained
import Data. Map as M
import Data. Set as S
import qualified Data. Foldable as FL

main :: IO ()
main = print $ fmap (constrained @Ord (+1))
             $ RMS ([(1,[11,21]),(2,[31,41])])

data RelationMS a b where
  IdRMS :: RelationMS a a
  RMS :: Map a (Set b) -> RelationMS a b 
deriving instance (Show a, Show b) => Show (RelationMS a b)

instance Category RelationMS where
    type Object RelationMS o = Ord o
    id = IdRMS
    RMS mp2 .  RMS mp1
      | M.null mp2 || M.null mp1 = RMS M.empty
      | otherwise = RMS $ M.foldrWithKey 
            (\k s acc -> M.insert k (S.foldr (\x acc2 -> case M.lookup x mp2 of
                                                        Nothing -> acc2
                                                        Just s2 -> S.union s2 acc2
                                             ) S.empty s
                                    ) acc
            ) M.empty mp1

(°) :: (Object k a, Object k b, Object k c, Category k) => k a b -> k b c -> k a c
r1 ° r2 = r2 .  r1

instance (Ord a, Ord b) => Semigroup (RelationMS a b) where
    RMS r1 <> RMS r2 = RMS $ M.foldrWithKey (\k s acc -> M.insertWith S.union k s acc) r1  r2 

instance (Ord a, Ord b) => Monoid (RelationMS a b) where
    mempty = RMS M.empty
    mappend = (<>)

instance Functor (RelationMS a) (ConstrainedCategory (->) Ord) Hask where
    fmap (ConstrainedMorphism f) = ConstrainedMorphism $
            \(RMS r) -> RMS $ M.map (S.map f) r

fldl :: (a -> Set b -> a) -> a -> RelationMS k b -> a
fldl f acc (RMS r) = M.foldl f acc r

fldMp :: Monoid b1 => (Set b2 -> b1) -> RelationMS k b2 -> b1
fldMp m (RMS r) = M.foldr (mappend .  m) mempty r

-- instance Foldable (RelationMS a) (ConstrainedCategory (->) Ord) Hask where
    -- foldMap f (RMS r)
        -- | M.null r = mempty
        -- | otherwise = FL.foldMap f r
    -- ffoldl f = uncurry $ M.foldl (curry f)

A:

You need FL.foldMap (FL.foldMap f) r in your definition so that you fold over the Map and the Set. 
However, there's a critical error in your Functor instance; your fmap is partial.  It's not defined on IdRMS. 
I suggest using -Wall to have the compiler warn you about such issues. 
The problem comes down to you need to be able to represent relations with finite and infinite domains.   IdRMS :: RelationRMS a a can already be used to represent some relations of infinite domain, it isn't powerful enough to represent a relation like fmap (\x -> [x]) IdRMS. 
One approach is to use Map a (Set b) for finite relations and a -> Set b for infinite relations. 
data Relation a b where
   Fin :: Map a (Set b) -> Relation a b
   Inf :: (a -> Set b) -> Relation a b

image :: Relation a b -> a -> Set b
image (Fin f) a = M.findWithDefault (S.empty) a f
image (Inf f) a = f a

This changes the category instance accordingly:
instance Category Relation where
  type Object Relation a = Ord a

  id = Inf S.singleton

  f .  Fin g = Fin $ M.mapMaybe (nonEmptySet .  concatMapSet (image f)) g
  f .  Inf g = Inf $ concatMapSet (image f) .  g

nonEmptySet :: Set a -> Maybe (Set a)
nonEmptySet | S.null s = Nothing
            | otherwise = Just s

concatMapSet :: Ord b => (a -> Set b) -> Set a -> Set b
concatMapSet f = S.unions .  fmap f .  S.toList

And now you can define a total Functor instance:
instance Functor (Relation a) (Ord ⊢ (->)) Hask where
  fmap (ConstrainedMorphism f) = ConstrainedMorphism $ \case -- using {-# LANGUAGE LambdaCase #-}
    Fin g -> Fin $ fmap (S.map f) g
    Inf g -> Inf $ fmap (S.map f) g

But a new issue raises its head when defining the Foldable instance:
instance Foldable (Relation a) (Ord ⊢ (->)) Hask where
  foldMap (ConstrainedMorphism f) = ConstrainedMorphism $ \case
    Fin g -> Prelude.foldMap (Prelude.foldMap f) g
    Inf g -> -- uh oh...problem! 

We have f :: b -> m and g :: a -> Set b. Monoid m gives us append :: m -> m -> m, and we know Ord a, but in order to generate all the b values in the image of the relation, we need all the possible a values! 
One way you could try to salvage this is to use Bounded and Enum as additional constraints on the relation's domain.  Then you could try to enumerate all the possible a values with [minBound..maxBound] (this may not be list every value for all types; I'm not sure if that's a law for Bounded and Enum). 
instance (Enum a, Bounded a) => Foldable (Relation a) (Ord ⊢ (->)) Hask where
  foldMap (ConstrainedMorphism f) = ConstrainedMorphism $ \case
    Fin g -> Prelude.foldMap (Prelude.foldMap f) g
    Inf g -> Prelude.foldMap (Prelude.foldMap f .  g) [minBound .. maxBound]

