So I can confirm that the issue is a problem with having the songs folder on an APFS volume. I realized this when I noticed that the custom icons dialog in Logic Pro X was all out of order as well. I copied my songs folder over to an HFS+ volume and, sure enough, the songs appeared in the correct order.

I don’t know enough about the file systems to tell what’s gone wrong. I’ve sent feedback to Apple so maybe it’ll get fixed in an update.