You already said you tried urlencode(), but what did you try that with? If you’ve only tried urlencode() with values from the_title() or the_title_attibute() so far, try it with get_the_title() directly. I’m able to get different results by trying this out if I try with a little test shortcode:
-
Using
the_title():
function wpse_123927_cb() { return urlencode( the_title() ); } add_shortcode('test_wpse_123927', 'wpse_123927_cb'); -
Using
the_title_attribute():
function wpse_123927_cb() { return urlencode( the_title_attribute() ); } add_shortcode('test_wpse_123927', 'wpse_123927_cb'); -
Using
get_the_title():
function wpse_123927_cb() { return urlencode( get_the_title() ); } add_shortcode('test_wpse_123927', 'wpse_123927_cb');
The third solution here works well both ways. I used this little code here to test:
function wpse_123927_cb() {
$encode = esc_attr( urlencode( get_the_title() ) );
$decode = urldecode($encode);
return 'Encoded: ' . $encode . '<br>Decoded: '. $decode;
}
add_shortcode('test_wpse_123927', 'wpse_123927_cb');
And got the following output: 
Hope that helps!