Аз бих си въвела нова променлива countCheckedBooks = 0; която да се увеличава след проверката дали си намерил книгата, за да не се обърква логиката с index :

function oldBooks(input){

    let index = 0;

    let countCheckedBooks = 0

    let myBook = input[index];

    index++;

    let nextBook = input[index];

    index++;

    let foundBook = false;

    while(nextBook != "No More Books"){

        if(nextBook === myBook){

            foundBook = true;

            break;

        }

        countCheckedBooks++;

        index++;

        nextBook = input[index];

    }

    if(foundBook === false){

        console.log("The book you search is not here!");

        console.log(`You checked ${countCheckedBooks} books.`);

    } else {

        console.log(`You checked ${countCheckedBooks} books and found it.`);

    }

}