I use your first method.
All my songs are ordered, with a set number and a position in the set.

I first put all my songs in major folders. Mine happen to be DECADE. so songs have 50-name, or 70-name. And they stay in that folder in alphabetical order.

I make sets of songs in folders by name, such as Anne Murray, or Ink Spots. I then drag songs from the decade folder to the particular set I need and put a sequence number on the front so I might have 01-50-name, followed by 02-70-next.

These will play in order, once you select the folder. When you no longer need the Ink Spot folder, for instance just delete the sequence number from the name and return it to the decade folder.

You could create 1 folder per gig or even 1 of known special requests such as Happy Birthday.

Switching between folders is time consuming, but certainly doable. Putting a complete evening set in one folder is practical. Adding a sequence number can be a chore but there is software out there that can help. I use "The Rename". It's free and work well.

BIAB for Windows Version 2019 (643)
Windows 10 (1909)