Finding all non-empty directories and their files on an SFTP server with Paramiko
There is nothing obviously wrong with your implementation that could explain a slow behaviour. The slowest part here being the use of listdir_attr, you might want to check with other means if its speed matches what your network has to offer.
That being said, there are a few changes you can do to improve a bit on your end:

use an helper function so files will not be both a return value and modified in place;
use paramiko simulation of a working directory to remove the need for os.path;
use list-comprehension to remove the need for defaultdict.

I'm also wondering whether you really want to list everything that is not a directory or only regular files (i.e. no symlinks, no block devives, etc.) You can change the proposed list-comprehension accordingly.
Proposed improvements
def _sftp_helper(sftp, files):
    stats = sftp.listdir_attr('.')
    files[sftp.getcwd()] = [attr.filename for attr in stats if stat.S_ISREG(attr.st_mode)]

    for attr in stats:
        if stat.S_ISDIR(attr.st_mode):  # If the file is a directory, recurse it
            sftp.chdir(attr.filename)
            _sftp_helper(sftp, files)
            sftp.chdir('..')

def filelist_recursive(sftp):
    files = {}
    _sftp_helper(sftp, files)
    return files

You can adapt easily to include back the optional path parameter into filelist_recursive.