Why does wp_redirect strip out %0A (url encoded new line character) and how do I make it stop?

If you take a look to the wp_sanitize_redirect() function you will notice it is removing the new lines from the destination URL:

https://core.trac.wordpress.org/browser/tags/4.9/src/wp-includes/pluggable.php#L1249

In my opinion you have 2 options:

1 – Convert new lines on the message to a diff allowed unique char combination and then replace them back to new lines before outputting the string from the responseMsg URL parameter.

2 – Since this is a pluggable function, you can put it on a plugin and customize it to fit your needs.
Something like this:

if ( !function_exists('wp_redirect') ) :
/**
 * Redirects to another page.
 *
 * Note: wp_redirect() does not exit automatically, and should almost always be
 * followed by a call to `exit;`:
 *
 *     wp_redirect( $url );
 *     exit;
 *
 * Exiting can also be selectively manipulated by using wp_redirect() as a conditional
 * in conjunction with the {@see 'wp_redirect'} and {@see 'wp_redirect_location'} hooks:
 *
 *     if ( wp_redirect( $url ) ) {
 *         exit;
 *     }
 *
 * @since 1.5.1
 *
 * @global bool $is_IIS
 *
 * @param string $location The path to redirect to.
 * @param int    $status   Status code to use.
 * @return bool False if $location is not provided, true otherwise.
 */
function wp_redirect($location, $status = 302, $strip_new_lines = true) {
    global $is_IIS;

    /**
     * Filters the redirect location.
     *
     * @since 2.1.0
     *
     * @param string $location The path to redirect to.
     * @param int    $status   Status code to use.
     */
    $location = apply_filters( 'wp_redirect', $location, $status );

    /**
     * Filters the redirect status code.
     *
     * @since 2.3.0
     *
     * @param int    $status   Status code to use.
     * @param string $location The path to redirect to.
     */
    $status = apply_filters( 'wp_redirect_status', $status, $location );

    if ( ! $location )
        return false;

    $location = wp_sanitize_redirect($location, $strip_new_lines);

    if ( !$is_IIS && PHP_SAPI != 'cgi-fcgi' )
        status_header($status); // This causes problems on IIS and some FastCGI setups

    header("Location: $location", true, $status);

    return true;
}
endif;

if ( !function_exists('wp_sanitize_redirect') ) :
/**
 * Sanitizes a URL for use in a redirect.
 *
 * @since 2.3.0
 *
 * @param string $location The path to redirect to.
 * @return string Redirect-sanitized URL.
 **/
function wp_sanitize_redirect($location, $strip_new_lines = true) {
    $regex = '/
        (
            (?: [\xC2-\xDF][\x80-\xBF]        # double-byte sequences   110xxxxx 10xxxxxx
            |   \xE0[\xA0-\xBF][\x80-\xBF]    # triple-byte sequences   1110xxxx 10xxxxxx * 2
            |   [\xE1-\xEC][\x80-\xBF]{2}
            |   \xED[\x80-\x9F][\x80-\xBF]
            |   [\xEE-\xEF][\x80-\xBF]{2}
            |   \xF0[\x90-\xBF][\x80-\xBF]{2} # four-byte sequences   11110xxx 10xxxxxx * 3
            |   [\xF1-\xF3][\x80-\xBF]{3}
            |   \xF4[\x80-\x8F][\x80-\xBF]{2}
        ){1,40}                              # ...one or more times
        )/x';
    $location = preg_replace_callback( $regex, '_wp_sanitize_utf8_in_redirect', $location );
    $location = preg_replace('|[^a-z0-9-~+_.?#=&;,/:%!*\[\]()@]|i', '', $location);
    $location = wp_kses_no_null($location);

    // remove %0d and %0a from location
    $strip = array('%0d', '%0a', '%0D', '%0A');
    return $strip_new_lines ? _deep_replace( $strip, $location ) : $location;
}

/**
 * URL encode UTF-8 characters in a URL.
 *
 * @ignore
 * @since 4.2.0
 * @access private
 *
 * @see wp_sanitize_redirect()
 *
 * @param array $matches RegEx matches against the redirect location.
 * @return string URL-encoded version of the first RegEx match.
 */
function _wp_sanitize_utf8_in_redirect( $matches ) {
    return urlencode( $matches[0] );
}
endif;

Then you can call:

// by default is removing new lines so we pass false
$strip_new_lines = false;
$location = "/upload_success?responseMsg=".urlencode($new_body->message);

// make sure you pass the correct HTTP 
// status here to prevent penalty or any  other SEO issue
$status = 302;

wp_redirect( $location, $status,  $strip_new_lines );
//  wp_redirect() does not exit automatically
exit;