The embedded carriage returns can be replaced with '\n' using this simple script on the Red Hat box:

use strict;
use warnings;

while (<>) {
    chomp;
    if (/^M$/) {
        print "$_\n";
    } else {
        print "$_\\n";
    }
}
[download]

'^M' is single character, entered pressing 'ctrl-v enter'.

Update: The direct conversion does not seem to be hopeless. You can simply omit the $converter if you do not need encoding conversion. I created an xlsx file with ~1.000.000 rows and with only two columns (file size ~10Mb) and it was converted to csv in 140sec.