Generating number of possibilites of popping two stacks to two other stacks
(answer for another problem, see the edit below)

First, generate all subsets $A_1$ of $A$. $A_1$ will go in $C$ and $A_2=A\backslash A_1$ in $D$. Likewise, generate all subsets $B_1$ of $B$. You then have to generate all possible ordered combinations of $A_1$ and $B_1$ for $C$ and the same for $A_2$ and $B_2$ in $D$.

This amounts to enumerate, given $(a_1,…,a_n)$ and $(b_1,…,b_m)$ all interleavings of length $n+m$ which can be viewed as an exploration of the intersections of a grid of size $n×m$. (There are $\frac{(n+m)!}{n!m!}$ paths)

This is a way of generating all possible $C$s and $D$s uniquely.

But maybe I misunderstood the question. Is this what you want? To help comparing with what you already have tried, here is the number of pairs of stacks it generates (where $A$ is the size of $A$):

$$N(A,B)=\sum_{n=0}^{A}\sum_{m=0}^{B}\binom{A}{n}\binom{B}{m}\frac{(n+m)!}{n!m!}\frac{(A+B-n-m)!}{(A-n)!(B-m)!}$$


Formula when $A=B$ on the OEIS.
Implementation in Haskell
Execution trace for A=["a", "b"] B=["1", "2"] with 54 pairs since $N(2,2)=54$




EDIT: I am wrong: my algorithm behaves like separating $A$ and $B$ into $(A_1,A_2)$ and $(B_1,B_2)$ before interleaving $(A_1,B_1)$ and $(A_2,B_2)$ which is presumably what you don't want (it generates too many stacks, e.g. from $A=[2,1], B=[4,3]$ it includes $C=[2,3],D=[4,1]$). 

(Mitchus's answer does not have this problem.)