Consider a branching Markov process with values in some general type space. Conditional on survival up to generation $N$, the genealogy of the extant population defines a random marked metric measure space, where individuals are marked by their type and pairwise distances are measured by the time to the most recent common ancestor. In the present manuscript, we devise a general method of moments to prove convergence of such genealogies in the Gromov-weak topology when $N \to \infty$. Informally, the moment of order $k$ of the population is obtained by observing the genealogy of $k$ individuals chosen uniformly at random after size-biasing the population at time $N$ by its $k$-th factorial moment. We show that the sampled genealogy can be expressed in terms of a $k$-spine decomposition of the original branching process, and that convergence reduces to the convergence of the underlying $k$-spines. As an illustration of our framework, we analyse the large-time behavior of a branching approximation of the biparental Wright-Fisher model with recombination. The model exhibits some interesting mathematical features. It starts in a supercritical state but is naturally driven to criticality. We show that the limiting behavior exhibits both critical and supercritical characteristics.