Unable to add account on android 6.0.1
Thanks to @Robert who pointed me in the right direction.
Unfortunately Google Play services didn't update itself automatically even though it had been on for a couple of days. So... I resorted to downloading a recent version from apkmirror, found the right version for the 2013 Asus Nexus 7 (armeabi-v7a, Android 6.0+, nodpi).
It took a minute or so to install but it was successful, after which I attempted to login again. This time, after entering my password, I was prompted to choose how I wanted to use my security key to login. Chose NFC, and I'm in.