Here are the "Possible reasons" listed in the error box, with comments:
1) Python is not installed.
It's not only installed, it's installed twice. Our shop standard is Python 2.7, but when I couldn't P4Python with that, I installed Python 3.5 as well. Both versions of Python are in the system path, but the EXEs are differently named so I can run either version from the command line. The 3.5 directory is first so that if the installer tries to load some other Python file it will find it in the 3.5 directory.
2) An unsupported version or architecture of Python is installed.
It's the 64 bit version of Python. It's version 3.5, the current stable version, instead of 3.3. I trust that P4Python isn't that fussy enough to complain about that. (It isn't, is it? Really?)
3) The folder containing the Python executable is not in the system path.
4) Another version or architecture of Python is in the system path before the supported version or architecture.
5) The P4Python install paths are not writable.
The installer doesn't explain what the P4Python install paths are (or even what "install paths," in the plural, means), so I can't answer this one way or the other. If it's referring to the Python program directory, it's as writable as it can get, because I ran the installer as Administrator.
So I appear to have ruled out every documented reason for the installer to fail. Why is it failing?