$\newcommand{\ket}[1]{|#1\rangle}$I figured out the answer while writing the question. The gist is
- Each batch of $n$ two-qubit states, after the measurement, results in a state that is a balanced superposition of $\binom{n}{k}$ orthogonal product states. We could regard this as equivalent to a maximally entangled state in a space of dimension $\binom{n}{k}$. Call this state $\ket{\Phi(n,k)}$.
- Furthermore, the result of doing this measurement on two different batches is that we get the state $\ket{\Phi(n,k_1)}\otimes\ket{\Phi(n,k_2)}$ for some $k_1,k_2$. But the product of two balanced states of this kind just gives a balanced state over a number of elements equal to the product of the individual numbers of elements. In other words, if $\ket{A}\equiv \sum_{i=1}^a|ii\rangle$ and $|B\rangle\equiv\sum_{i=1}^b \ket{ii}$, then
$$\ket A\otimes\ket B = \sum_{i=1}^a\sum_{j=1}^b \ket{ij}\otimes \ket{ij} \equiv \sum_{k=1}^{ab}\ket k\otimes\ket k,$$
up to a redefinition of the basis states in the last step.
- So if $m$ is such that $\prod_{i=1}^m \binom{n}{k_i}\simeq 2^\ell$, that means that the corresponding state is $\bigotimes_{i=1}^m \ket{\Phi(n,k_i)}$, which as per our reasoning above can be written as
$$\bigotimes_{i=1}^m \ket{\Phi(n,k_i)} \simeq \sum_{k=1}^{2^\ell} \ket k\otimes \ket k.$$
This state can now be readily converted into $\ell$ singlets.
More formal description --- Say we have $n$ copies of a two-qubit pure state of the form . The correponding $(2n)$-qubit state is thus
$$\ket{\Psi} \equiv \bigotimes_{i=1}^n\ket\psi
= \sum_{k=0}^n \sqrt{\binom{n}{k}}\alpha^k \beta^{n-k} \ket{\Phi(n,k)},\tag1$$
where $\ket{\Phi(n,k)}$ is the balanced superposition over all possible $(2n)$-qubit computational basis states where each party has $k$ zeros.
More precisely,
$$\ket{\Phi(n,k)} \equiv \frac{1}{\sqrt{\binom{n}{k}}} \sum_{I\in S(n,k)} |I\rangle_A\otimes|I\rangle_B,$$
with $\ket{I}_A,\ket{I}_B$ both $n$-qubit states, and with the sum over $I$ extended over the set $S(n,k)$ of all $n$-qubit computational basis states with $k$ zeros (of which there's $\binom{n}{k}$, hence the normalisation factor).
For example,
$$\ket{\Phi(3,2)}\equiv \frac{1}{\sqrt{\binom{3}{2}}} (\ket{100}\otimes \ket{100} + \ket{010}\otimes \ket{010}+ \ket{001}\otimes \ket{001}).$$
We now take $m$ batches of these $(2n)$-qubit states, performing a projective measurement on each one individually that projects the state into one of the $\ket{\Phi(n,k)}_A\otimes \ket{\Phi(n,k)}_B$ states, for some $k$.
We take $m$ such that
$$D_m \equiv \prod_{j=1}^m \binom{n}{k_j} \simeq 2^\ell$$
for some $\ell$. Or more precisely, we require $2^\ell\le D_m\le 2^\ell(1+\epsilon)$ for some small $\epsilon$.
Local unitary operations --- The only thing missing is the final local unitary operation to obtain the singlets. We want to apply this on the state obtained after the measurement, namely, up to renormalisation,
$$\bigotimes_{i=1}^m \ket{\Phi(n,k_i)}
= \sum_{I_j\in S(n, k_j)} \ket{I_1,..., I_m}\otimes \ket{I_1,..., I_m}. \tag2$$
For comparison, a product of singlets $\ket{\Phi^+}\equiv\ket{00}+\ket{11}$ has the form
$$\sum_{i_1=0}^1 \cdots \sum_{i_\ell=0}^1 \ket{i_1,...,i_\ell}\otimes\ket{i_1,...,i_\ell}
= \sum_{I=0}^{2^\ell-1} \ket I\otimes \ket I.\tag3$$
Given any bijective map sending the indices in the sum in (2) into the indices in the sum of (3), we can build a corresponding $2^\ell\times2^\ell$ unitary, which will achieve the conversion.
