Isso é uma coisa difícil de resolver a uma grande distância. Possivelmente (e espero) o disco rígido não foi realmente formatado, mas apenas a tabela de partições mudou. Se sua partição NTFS foi definida como RAW, talvez seja possível definir o tipo novamente como NTFS usando algum utilitário como gparted . Se você olhar a página inicial, poderá encontrar uma versão USB inicializável (várias outras também).
A alteração da partição não deve alterar nada para o conteúdo do disco.
Atualização: Se você selecionou 'Excluir todos os dados', todos os dados foram realmente sobrepostos e duvido que você encontre alguma coisa. Este processo levou provavelmente vários minutos (ou mais). O principal objetivo aqui é detectar erros no disco rígido, que podem escapar sem serem detectados com o método 'Format partition'.
Este método, 'quick format', apenas inicializa setores que são usados para acesso administrativo (ou seja, 'dir' e outros) ao disco, e deixa os dados sozinhos. Há uma pequena chance de que você possa se recuperar disso, mas perderia toda a "estrutura" - arquivos grandes seriam cortados em partes pequenas e você teria que juntá-los novamente.
Em pânico, um amigo meu me trouxe um disco com centenas de pequenos arquivos de dados (< 4kB, texto), que compunham seu projeto. Felizmente eles eram pequenos e eu poderia recuperá-los. E eu poderia até mesmo renomeá-los, já que o nome estava dentro do arquivo de texto. Eu nem sonharia em recuperar um mp4.
Então, me desculpe, mas basicamente isso é uma má notícia. O bom aspecto é que o formato lento não encontrou nada de errado com o seu disco, mas isso não é muito confortável ...