You regular expression doesn't specify a control character, it removes a ^ followed by an M. To get rid of the control-M's, use either \cM to specify a control-M, or the special escape character \r, which indicates the same thing. Or do it all on one line like this:

perl -pi.orig -e 's/\r$//' <filenames>
[download]

You can also do it directly in vi using ':%s/^V^M//g' (where ^V and ^M are literal control characters, hit control-V followed by control-M).