Ugg, I had to spend a fair amount of time coming up with a good example. Hope this is helpful!

The Monoid operation mappend is guaranteed to be associative, so the order is irrelevant. Data structures can fold in whatever way is most efficient for their structure.

It's true that lists and arrays are implemented as right folds, however the fold implementation for sets is neither:

From Data.Set:

  fold = go
    where go Tip = mempty
          go (Bin 1 k _ _) = k
          go (Bin _ k l r) = go l `mappend` (k `mappend` go r)

  -- Here, I reorganized the code of `fold` to have the same shape as
  -- `foldl/foldr` so that you can see the difference in structure more
  -- clearly.
  fold2 = fold3 mappend mzero
  fold3 f z = go z
    where
      go z' Tip           = z'
      go z' (Bin _ x l r) = f (go f z' l) (f x (go f z' r))

  foldl f z = go z
    where
      go z' Tip           = z'
      go z' (Bin _ x l r) = go (f (go z' l) x) r

  foldr f z = go z
    where
      go z' Tip           = z'
      go z' (Bin _ x l r) = go (f x (go z' r)) l

I went through some examples to make 100% sure that fold has different behavior than foldl/foldr:

  fold      [[_ 4 _] 3 _] → f 4 (f 3 #)
  fold2 f # [[_ 4 _] 3 _] → f (f # (f 4 #)) (f 3 #)
  foldl f # [[_ 4 _] 3 _] → f (f # 4) 3
  foldr f # [[_ 4 _] 3 _] → f 3 (f 4 #)

Reductions:

  fold [[_ 4 _] 3 _]
  f    (go [_ 4 _])  (f 3 (go []))
  f    4             (f 3 (go []))
  f    4             (f 3 #)

  fold2 [[_ 4 _] 3 _]
  fold3 f                       #             [[_ 4 _] 3 _]
  f     (go [_ 4 _])            (f 3 (go _))
  f     (f (go _) (f 4 (go _))) (f 3 (go _))
  f     (f #      (f 4 #     )) (f 3 #     )
  f     (f #      (f 4 #     )) (f 3 #     )
  f (f # (f 4 #)) (f 3 #)

  foldl f                     #             [[_ 4 _] 3 _]
  go    #                     [[_ 4 _] 3 _]
  go    (f (go # [_ 4 _]) 3)  _
  f     (go # [_ 4 _])        3
  f     (go (f (go # _) 4) _) 3
  f     (go (f # 4) _)        3
  f     (f # 4)               3

  foldr f                    #                      [[_ 4 _] 3 _]
  go    #                    [[_ 4 _] 3 _]
  go    (f 3 (go # [_ 4 _])) _
  f     3                    (go # [_ 4 _])
  f     3                    (go (f 4 (go # _)) _)
  f     3                    (f 4 (go # _))
  f     3                    (f 4 #)

It's useful for more general folds over more general types. If you have a tree structure then you might not want to fold from the left or the right but instead in multiple places in parallel and then combine them at the end

    * + (* + (* + (* + (* + (* + *)))))   versus
    (((((* + *) + *) + *) + *) + *) + *   versus
    ((* + *) + *) + (* + (* + *))

Oh God, right. The changes over the years have left me bamboozled. Is (.) fmap yet?