Is there a decidable algorithm to compose two well-behaved recursive functions that work on a recursive tree datatype?
If the functions are sufficiently well-behaved, as in your example, you can express f and g as regular transducers for trees.  Then you can compute the composition of two such transducers, which will also be a regular transducer (I believe), and convert it back to a Haskell function.

Another approach: in some cases, simple let-substitution might suffice.  For instance, given your f and your g, we can identify their composition fg via the following sequence of steps.  We know fg = f . g, so plugging in the definition of g, we get:

fg A = f(g(A)) = f A
fg (B x) = f(g(B x)) = f(B (B (B (g x))))


Now plugging in the definition of f, we get:

fg A = A
fg (B x) = B (B f(B (B (g x))))


Continuing to plug in the definition of f, we get:

fg A = A
fg (B x) = B (B (B B( f(B (g x)))))


And plugging in the definition of f once more:

fg A = A
fg (B x) = B (B (B B( (B (B (f(g x))))))


which simplifies to

fg A = A
fg (B x) = B (B (B (B (B (B (fg x)))))


And now you have your desired recursive definition of their composition.  Notice that this is the same as the function h you wanted to get out.  As far as I know, there's no guarantee that this procedure will always work, but it is easy enough to apply.