So I upgraded a VM running on Parallels on my M1, only to be greeted with:

This issue seems not to be unique to Parallels. It also happens with UTM. The quick fix here was to boot the machine with the previous kernel and customize grub to boot using GRUB_DEFAULT=saved and GRUB_SAVEDEFAULT=true for as long as the issue persists.
Granted this does not work when trying to install from an Ubuntu 20.04.4 ISO image, but you can start from an older one for as long as the issue persists.
Update: kernel
Linux upwork-box 5.4.0-105-generic #119-Ubuntu SMP Mon Mar 7 18:50:13 UTC 2022 aarch64 aarch64 aarch64 GNU/Linux
seems to work