To insert hard newlines in Emacs from within the minibuffer, the simplest method is to turn off the longlines-mode, then use C-QC-J for the newline character, and then turn longlines-mode back on.

In slightly more detail, suppose you wanted to replace all those ^Ms in a document by newlines. Then one simple way is:

replace-string C-QC-M C-QC-J

but with the longlines mode, this creates soft newlines. The only way I can find to create hard newlines is to turn off longlines-mode, do the above, and then turn longlines-mode back on.