Abstract Super-moiré materials represent a novel playground to engineer states of matter beyond the possibilities of conventional moiré materials. However, from the computational point of view, understanding correlated matter in these systems requires solving models with several millions of atoms, a formidable task for state-of-the-art methods. Conventional wavefunction methods for correlated matter scale with a cubic power with the number of sites, a major challenge for super-moiré materials. Here, we introduce a methodology capable of solving correlated states in super-moiré materials by combining a kernel polynomial method with a quantics tensor cross interpolation matrix product state algorithm. This strategy leverages a mapping of the super-moiré structure to a many-body Hilbert space, that is efficiently sampled with tensor cross interpolation with matrix product states, where individual evaluations are performed with a Chebyshev kernel polynomial algorithm. We demonstrate this approach with interacting super-moiré systems with up to several millions of atoms, showing its ability to capture correlated states in moiré-of-moiré systems and domain walls between different moiré systems. Our manuscript puts forward a widely applicable methodology to study correlated matter in ultra-long length scales, enabling rationalizing correlated super-moiré phenomena.