Those work for me:

#!/usr/bin/perl

use feature qw/say/;
use warnings;
use strict;
use Encode;

my $str = "=C3=9C =C3=9F";

say decode('MIME-Header', "=?iso-8859-1?Q?" . $str . "?=");
[download]

Output:

$ perl 1092761.pl
Ü ß
$
[download]

Are you sure your the encoded data's correct? The string should contain the UTF-8 encoding of the character, in essence (for instance, "ß" is C3 9F in UTF-8, so it's encoded as =C3=9F).