apt automatically removing dependencies by default is such a trap, I much prefer pacman's behaviour of refusing to remove package that breaks dependecies unless explicitly told to do so.
apt will not automatically remove dependencies either.
I suspect the OP already had ubuntu-desktop package removed for some other reason, and there was no direct dependency on evolution-data-server for gdm: it will only remove dependencies which no other still-installed package depends on. That might still mean a packaging bug (but at least on 18.04, attempting to remove evolution-data-server prompts me how it's going to remove gdm3 too — sure, it's short and easily missed; attempting to remove evolution does not attempt to remove evolution-data-server since a bunch of other stuff depends on it like gnome-calendar too).
In any case, apt will prompt you about all the packages you are about to remove (unless you pass "-y(es)" to it).
Great! That UI was horrific. Hitting a key like spacebar didn’t unlock.
Aside: I completely broke the Ubuntu login screen yesterday. I did `apt remove evolution*`. Unfortunately the login screen depends on evolution-data-server, so I couldn’t login from lock screen, and after reboot it dropped me to TTY!! Gnome is just getting crazy - it would be like Windows login depending on MS Outlook! Gnome is a big ball of interdependencies, becoming more like Windows. I get it, but I don’t like it. Edit: FYI: fixed in TTY3 (ctrl-alt-F3) by `apt install --reinstall ubuntu-desktop` from memory.