How to filter the contacts by phone number on Android 5.1
I know it's a sub-optimal workaround, but I wrote a script for myself that I thought was worth sharing. This will filter an exported contacts file. To use go to Contacts > Import/Export > Export to storage, and copy the file to an environment equipped with python.

Edit the script to read from the exported file and write to an unused path, then delete all your contacts and import the filtered file back in.

    READPATH = 'D:/ContactsBackup.vcf'
    WRITEPATH = 'D:/ContactsFiltered.vcf'

    vcard = ''
    vcards = []

    for line in open(READPATH):
        vcard += line
        if 'END:VCARD' in line:
            if 'TEL' in vcard:  # Append contact if it has phone number.
                vcards.append(vcard)
            vcard = ''  # Reset read-cache.

    with open(WRITEPATH, 'w') as file:
        file.write(''.join(vcards))