This happened starting today on both my Macs. I am worried that if this keeps happening I might be somewhere without Internet access when it happens again and then cannot use any VMs until I have Internet access again.
No, I cannot. I typed my user name and password and Parallels was working again. I am sure you know what the screen looks like. It's the normal screen used to register Parallels Desktop.
Of course, we are familiar with that screen's appearance - we just needed to confirm at which point exactly that screen appeared (i.e., when as soon as Parallels Desktop application was launched or really only when you attempted starting the VM, etc.,). Please reboot the Mac once and check if the issue persists. If yes, remove and reinstall Parallels once.