Looks like this function suffers from the same bug as mb_encode_mime() with long strings of non us-ascii characters. The function then returns false. This applies for utf-8 to utf-8 "conversion".
<?php
$subject = 'Вы находитесь здесь: Главная > продукт';
$prefs = array(
'scheme' => 'Q',
'input-charset' => 'UTF-8',
'output-charset' => 'UTF-8',
'line-length' => 76,
'line-break-chars' => "\r\n",
);
echo 'Original: ' . $subject . PHP_EOL;
$enc = iconv_mime_encode( 'Subject', $subject, $prefs );
var_dump( $enc ); ?>
As a workaround, you could explode() the value on spaces and encode each word separately. Then remove the "Subject: " in front of the resulting strings and join() them with "\r\n " (don't forget the SPACE after the \n) as separator.