^M
é um EOL específico do Windows (End Of Line) e consiste em dois caracteres: retorno de carro \r
e nova linha \n
. Então você deve incluir \ n em seu comando replace também:
%s/\r\n//g
Se você quiser ficar com o comando original replace, primeiro deverá converter o formato EOL do seu arquivo do Windows one para o Unix one. Você pode usar a ferramenta dos2unix para fazer isso:
$ dos2unix fileToConvert