Ok, agora eu entendi:
- Baixado e iniciado jre-8u101-windows-i586.exe
- A instalação falhou na segunda etapa com um código de erro, mas enquanto o instalador ainda estiver aberto, eu poderia encontrar um jre1.8.0_101.msi onde o processo de desinstalação procura por jre1.8.0_101full.msi (observe a diferença no nome)
- Copiou o arquivo para um diretório diferente e renomeou como jre1.8.0_101full.msi
- Encerrou o instalador (o diretório e o jre1.8.0_101.msi foram excluídos)
- Iniciei o processo de desinstalação e alterei o caminho para o novo diretório.
Obrigado @Biswapriyo pela sua ajuda!