Non-monogamous mating behaviors including polygyny or extra-pair paternity are theorized to amplify sexual selection, since some males attract multiple mates or copulate with paired females. In several well-studied songbird species, females prefer more complex songs and larger repertoires; thus, non-monogamous mating behaviors are predicted to accelerate song evolution, particularly toward increased complexity. However, studies within songbird clades have yielded mixed results, and the effect of non-monogamy on song evolution remains unclear. Here, we construct a large-scale database synthesizing mating system, extra-pair paternity, and song information and perform comparative analyses alongside songbird genetic phylogenies. Our results suggest that polygyny drives faster evolution of syllable repertoire size (measured as average number of unique syllables), but this rapid evolution does not produce larger repertoires in polygynous species. Instead, both large and small syllable repertoires quickly evolve toward moderate sizes in polygynous lineages. Contrary to expectation, high rates of extra-pair paternity coincide with smaller repertoires.