StringMap.hs

{-# LANGUAGE RankNTypes, TypeFamilies, ConstraintKinds #-}
import Data.String
import Data.String.ToString
import Text.XML.HXT.Arrow.Pickle
import GHC.Exts

import qualified Data.Map.Strict as SM

f :: (C map key, C map String, XmlPickler (map String value), IsString key, ToString key)
        => (forall k k'. C map k => (k -> k') -> map k value -> map k' value)
        -> PU (map key value)
f mapKeys = xpWrap (mapKeys fromString, mapKeys toString) xpickle

type family C (m :: * -> * -> *) :: * -> Constraint
type instance C SM.Map = Ord

instance (Ord a, IsString a, ToString a, XmlPickler b) => XmlPickler (SM.Map a b) where
  xpickle = f SM.mapKeys

Hello.hs:18:15:
    Could not deduce (Ord k') arising from a use of ‘SM.mapKeys’
    from the context (Ord a, IsString a, ToString a, XmlPickler b)
      bound by the instance declaration at Hello.hs:17:10-81
    or from (C SM.Map k)
      bound by a type expected by the context:
                 (C SM.Map k) => (k -> k') -> SM.Map k b -> SM.Map k' b
      at Hello.hs:18:13-24
    Possible fix:
      add (Ord k') to the context of
        a type expected by the context:
          (C SM.Map k) => (k -> k') -> SM.Map k b -> SM.Map k' b
        or the instance declaration
    In the first argument of ‘f’, namely ‘SM.mapKeys’
    In the expression: f SM.mapKeys
    In an equation for ‘xpickle’: xpickle = f SM.mapKeys
Failed, modules loaded: none.

You also need a C map k' constraint on the higher-order function. In fact, I think you only need it on k', not k.