Pra receber essa notificação, não é necessário passar pela primeira etapa da senha. Ao digitar a senha errada, o Google fornece algumas opções de recuperação de conta e uma delas é receber a notificação no celular (quando esta opção está ativa nas configurações de conta).
Eu passo por isso, existe um homônimo que acha que possui o meu endereço de e-mail (que é simples, por eu ter esta conta logo no lançamento do serviço). Então de tempos em tempos recebo este aviso, ou então a criação de uma conta na Netflix, ou recuperação de senha do Mercado Livre… Enfim, eu já desisti de tentar fazer alguma coisa a respeito, eu simplesmente ignoro todos os avisos, pois não existe nada a fazer.