Monomial decomposition as product of smaller monomials
For the moment, let's restrict to counting these factorizations, rather than listing them.  Warming up with the one-variable case, integer partitions give the answer, as you point out.  You can compute the number $p(n)$ of partitions of $n$ using the generating function
$$\sum_n p(n)x^n = \prod_{i&gt;0} \frac{1}{1-x^i}.$$
This generalizes easily to two variables.  If $p(m,n)$ is the number of "partitions" of the 2-long vector $(m,n)$ (i.e. representations of $(m,n)$ as a sum of positive integral multiples of vectors of the form $(i,j)$ with $i,j\ge0$ and $i+j&gt;0$), then
$$\sum_{m,n} p(m,n)x^m y^n = \prod_{i,j\ge0;\ i+j&gt;0} \frac{1}{1-x^i y^j}.$$
The sequence $p(m,n)$ appears as A054225 in the OEIS.

If you want to list the factorizations rather than count them, look instead at
$$\prod_{i,j\ge0;\ i+j&gt;0} \frac{1}{1-u_{i,j}\ x^i y^j}.$$
For example, the coefficient of $x^2 y^2$ here is
$$u_{2,2} + u_{2,1}u_{0,1} + u_{2,0}u_{0,2} + u_{2,0}u_{0,1}^2 + u_{1,2}u_{1,0} +
  u_{1,1}^2 + u_{1,1}u_{1,0}u_{0,1} + u_{1,0}^2u_{0,2} + u_{1,0}^2 u_{0,1}^2,$$
corresponding to the 9 factorizations of the monomial $x^2 y^2$.

In principle you could write down a two-dimensional recurrence for $p(m,n)$ which is analogous to the recurrence for the ordinary partition numbers.  However, for it to be algorithmically useful (e.g. more efficient than computing the series expansion above), one would need a closed form for the coefficient of $x^m y^n$ in the product
$$\prod_{i,j\ge0;\ i+j&gt;0} (1-x^i y^j).$$