Quickly obtaining sums of sets of numbers
I believe that we can do even better than this answer, but perhaps this will help.

We split our list of bits $a_1$, $a_2$, $\dots$, $a_n$ into approximately $n / \beta$ collections (these could also be called groups, but I make the distinction so that we know that these are different from the groups above).  Here we set $\beta = \log{(m/(\log{(mn)})}$ In other words, the first collection consists of the first $\beta$ bits $a_1$, $a_2$, $\dots$, $a_{\beta}$.  The second collection consists of the second $\beta$ bits $a_{\beta+1}$, $a_{\beta+2}$, $\dots$, $a_{2\beta}$, and so on.

We find all possible sums for each collection, of which there are approximately $2^{\log{(m/(\log{(mn)}))}} = m/(\log{(mn)})$.  We then calculate each of these sums exactly.  If we're careful, we can calculate each sum in constant time by adding or subtracting one bit from a sum with all other bits the same.

Thus we use roughly $m/(\log{(mn)})$ space to store each solution, times $\log{\log{(mn)}}$ maximum bits per solution, times $n / \log{(mn)}$ different collections.

The running time should be approximately $O \left( \frac{mn \log{ \log{ (mn)}}}{\log{(mn)})^2} \right)$ if I did my calculations right.

This is somewhat faster than the naive approach.  Again, I believe that we can do better.