Accurate prediction of protein complex structures by AlphaFold3 and similar programs has been successfully used to predict the presence of protein-protein interactions (PPIs), but this technique has never been applied to an entire genome due to onerous computational requirements. Here we present pooled-PPI prediction, a technique that reduces the inference time of genome-scale screens ~2-fold and the number of jobs ~100-fold, and use it to predict the structure of all 113,050 pairwise PPIs in Mycoplasma genitalium using only 2,027 AlphaFold3 jobs. This unbiased dataset revealed a previously unappreciated but widespread size bias in AlphaFold interface scores, was highly predictive of known interactions, correctly identified protein-protein interfaces in macromolecular complexes, and uncovered new biology in M. genitalium. This work establishes pooled-PPI prediction as a highly scalable method for uncovering protein-protein interactions and a powerful addition to the functional genomics toolkit.