Counting reversibly using few FullAdders and little work space
Here is a construction with $3N + O(\lg N)$ adder computations/uncomputations and $2 \lg(N)$ ancilla usage.


Divide the input into $N/\lg N$ groups of size $\lg N$.
Allocate a result register of size $\lg N$.
For each group $g$:


Use the naive strategy to compute $g$'s weight using $\lg N$ adder computations and space.
Add the weight into the result register using $\lg N$ adder computations and uncomputations.
Uncompute $g$'s weight using $\lg N$ adder uncomputations.

The result register now contains the total weight.


The inner loop uses $3 \lg N$ adders, and runs $N / \lg N$ times, for a total of $3N$ adders. Half of the $2 \lg N$ ancilla bits are for the result register, and the other half are for the group weight computations.

Basically, using groups of size $\lg N$ instead of $\sqrt{N}$ gives an exponential improvement in space usage but only a constant factor loss in adders.