Can I write `foldr` (or `foldMap`) in terms of 'recursion schemes' `cata`?

foldMap, being the fundamental operation of Foldable, is a better candidate for implementation than foldr. The answer is a qualified yes. cata only handles recursion; it doesn't tell you where to "find" all the values in a structure. (In the same way, implementing foldMap @[] with foldr still requires knowing the inner details of [].) Doing so requires a little help:

class Bifoldable f where
  bifoldMap :: Monoid m => (a -> m) -> (b -> m) -> f a b -> m

You can then define

foldMapDefault ::
  (Recursive (f a), Base (f a) ~ b a, Bifoldable b) =>
  Monoid m => (a -> m) -> f a -> m
foldMapDefault f = cata (bifoldMap f id)

This allows you to do things like

data Tree a = Leaf | Branch (Tree a) a (Tree a)
makeBaseFunctor ''Tree
deriveBifoldable ''TreeF
instance Foldable Tree where foldMap = foldMapDefault

(Though you may as well have just said deriving Foldable on Tree.) For maximum genericity, you may want something more like this (I say "want"...)

newtype Fixed f a = Fixed { getFixed :: f a }
newtype Bibase f a b = Bibase { getBibase :: Base (f a) b }
instance (forall a. Recursive (f a), Bifoldable (Bibase f)) =>
         Foldable (Fixed f) where
  foldMap :: forall a m. Monoid m => (a -> m) -> Fixed f a -> m
  foldMap f = cata (bifoldMap f id . Bibase @f @a @m) . getFixed

You can now say things like

data Tree a = Leaf | Branch (Tree a) a (Tree a)
makeBaseFunctor ''Tree
deriveBifoldable ''TreeF
deriving via TreeF instance Bifoldable (Bibase Tree)
deriving via (Fixed Tree) instance Foldable Tree

But now your Base functors can be more irregular:

data List a = Nil | Cons a (List a)
type instance Base (List a) = Compose Maybe ((,) a)
instance Recursive (List a) where
  project Nil = Compose Nothing
  project (Cons x xs) = Compose (Just (x, xs))
instance Bifoldable (Bibase List) where
  bifoldMap f g (Bibase (Compose Nothing)) = mempty
  bifoldMap f g (Bibase (Compose (Just (x, xs)))) = f x <> g xs
deriving via (Fixed List) instance Foldable List

You often can, but not universally. All it takes is a single counter-example. Several exist, but consider the simplest one that comes to (my) mind.

While completely unnecessary, you can define Boolean values with an F-algebra:

data BoolF a = TrueF | FalseF deriving (Show, Eq, Read) 

instance Functor BoolF where      
  fmap _  TrueF =  TrueF
  fmap _ FalseF = FalseF

From this (as the linked article explains) you can derive the catamorphism:

boolF :: a -> a -> Fix BoolF -> a
boolF x y = cata alg
  where alg TrueF = x
        alg FalseF = y

The type Fix BoolF is isomorphic to Bool, which isn't parametrically polymorphic (i.e. it doesn't have a type parameter), yet a catamorphism exists.

The Foldable type class, on the other hand, is defined for a parametrically polymorphic container t, e.g.

foldr :: (a -> b -> b) -> b -> t a -> b

Since Bool isn't parametrically polymorphic, it can't be Foldable, yet a catamorphism exists. The same is true for Peano numbers.

---

For parametrically polymorphic types, on the other hand, you often (perhaps always?) can. Here's a Foldable instance for a tree defined with its catamorphism:

instance Foldable TreeFix where
  foldMap f = treeF (\x xs -> f x <> fold xs)

Here's one for Maybe:

instance Foldable MaybeFix where
  foldMap = maybeF mempty

and one for linked lists:

instance Foldable ListFix where
  foldr = listF