Неправильно парсишь, первым элементом передаешь селектор, а вторым html-код или документ, где надо найти.
Например:
$('#test', '<div class="b"><div id="test"></div></div>').length;
Но надо понимать, что jQuery не умеет искать на верхнем уровне. Например, так ты ничего не найдешь:
$('.b', '<div class="b"><div id="test"></div></div>').length;
Если нужен поиск по всему дереву, лучше использовать DOMParser для предварительного парсинга:
doc = new DOMParser().parseFromString('<div class="b"><div id="test"></div></div>', 'text/html');
$('.b', doc).length;
В твоем же случае можно поступить проще и просто обернуть ответ в еще один div:
$(document).on('click', 'a', function(){
    $.ajax({
        url: $(this).attr('href'),
        dataType: 'html',
        success: function(data) {
            console.log($(data)); //Тут выводиться ниже в скрине
            console.log($('<div>'+data+'</div>').find('#pagination')); // Должно найти
        }
    });
    return false;
});
P. S. Если ТОЧНО знаешь, что нужный элемент находится на верхнем уровне, то можно использовать фильтр:
$(document).on('click', 'a', function(){
    $.ajax({
        url: $(this).attr('href'),
        dataType: 'html',
        success: function(data) {
            console.log($(data)); //Тут выводиться ниже в скрине
            console.log($(data).filter('#pagination')); // Должно найти
        }
    });
    return false;
});