So this "erecovery" never worked in any way for me (the one which offers you to download the latest version).
Instead you need the normal recovery you already used. Formatting failed for me the first time too, try it again and then it will try to format "low-level" which worked for me.
Go...