Encountered softlock while playing.  Was on a huge map with 9 other empires (10 total).

I was not focused on religion at all, and when I finally hit 35 followers as a result of taking over a city, the game prompted me to pick a new tenet.  However, all of the tenets were already taken (one empire already had Tier 4s...) so I was unable to pick one.  The game would not let me skip this to end the turn, so I was unable to do anything else.

Just encountered the same issue. I had it in a 10 player game when reaching Tier 1 tenets after all 8 tenets were picked

Same problem here, seems like my game just ended...

There's maybe something you can try: in the game settings, there's an option called "mandatory on/off". Set it on "off" so the game doesn't force you to do certain things like picking a tech to research, buildings for idle cities, etc before finishing your turn. That should work for tenets as well.