shellcheck is advising not to use basename: why?

It's not about efficiency -- it's about correctness. basename uses newlines to delimit the filenames it prints out. In the usual case when you only pass one filename, it adds a trailing newline to its output. Since filenames may contain newlines themselves, this makes it difficult to correctly handle these filenames.

It's further complicated by the fact that people usually use basename like this: "$(basename "$file")". This makes things even more difficult, because $(command) strips all trailing newlines from command. Consider the unlikely case that $file ends with a newline. Then basename will add an extra newline, but "$(basename "$file")" will strip both newlines, leaving you with an incorrect filename.

Another problem with basename is that if $file begins with a - (dash a.k.a. minus), it will be interpreted as an option. This one is easy to fix: $(basename -- "$file")

The robust way of using basename is this:

# A file with three trailing newlines.
file=$'/tmp/evil\n\n\n'

# Add an 'x' so we can tell where $file's newlines end and basename's begin.
file_x="$(basename -- "$file"; printf x)"

# Strip off two trailing characters: the 'x' added by us and the newline added by basename. 
base="${file_x%??}"

An alternative is to use ${file##*/}, which is easier but has bugs of its own. In particular, it's wrong in the cases where $file is / or foo/.

The relevant lines in shellcheck's source code are:

checkNeedlessCommands (T_SimpleCommand id _ (w:_)) | w `isCommand` "dirname" =
    style id "Use parameter expansion instead, such as ${var%/*}."
checkNeedlessCommands (T_SimpleCommand id _ (w:_)) | w `isCommand` "basename" =
    style id "Use parameter expansion instead, such as ${var##*/}."
checkNeedlessCommands _ = return ()

There is no explanation given explicitly but based on the name of the function (checkNeedlessCommands) it looks like @jordanm is quite right and it is suggesting you avoid forking a new process.

dirname, basename, readlink etc (thanks @Marco - this is corrected) can create portability problems when security becomes important (requiring security of the path). Many systems (like Fedora Linux) place it at /bin whereas others (like Mac OSX) place it at /usr/bin. Then there is Bash on Windows, eg cygwin, msys, and others. It's always better to stay pure Bash, when possible. (per @Marco comment)

BTW, thanks for the pointer to shellcheck, I haven't seen that before.