A quick search didn't really yield any viable results. www.pdmusic.org seems to be a possibility, but it doesn't really seem to have many songs that would be well suited for children. Similarly, Project Gutenberg only seems to have classical music, and only in sheet music form, although that in itself might not be a bad thing. Finally, www.archive.org didn't yield any significant results.

In the puppet, it just changes as soon as it runs out of notes from the current song. It might be better to have something in-between each song, like some applause or something similar, that creates a clear distinction. That way we don't end up raising children that think "BINGO" and "Row Row Row your boat" are parts of the same song.