Counting the number of binary solutions of quadratic system
Actually, it would appear that a standard breadth-first search works for this specific problem.

The algorithm tracks all the solutions that satisfy the equation up to bit $n$, and for each such solution, it considers all possible extensions to bit $n+1$ (there are four), and whether they satisfy the condition on $c_{n+1}$.

If you use this algorithm on the standard factorization problem, it fails miserably (as the number of intermediate solutions approximately doubles at each step until you hit the half-way point); this happens because each extension satisfies the next condition with probability 0.5.  However, for this problem, the condition that needs to be satisfied is $\sum_{i+j=k}p_iq_j = c_k$, which for large $k$ has a considerably smaller probability of holding for an incorrect solution, and hence incorrect solutions are pruned much faster.

I threw together an implementation, and it showed promise; given the arbitrarily product $314159 \times 271829$, such a state search gave a maximum of 22 intermediate solutions (11, really, as I counted solutions with swapped $p$ and $q$ separately), and this was after processing bit 11.

This finds all the solutions fast enough that you should be able to use this to obtain a count.