Use apenas os curingas do shell no padrão de pesquisa do locate - essa funcionalidade é um recurso histórico do utilitário e deve ser suportada em todos os sistemas.
Por exemplo:
$ locate '*/dirname/*filename*'
Certifique-se de usar as estrelas ao redor da string de pesquisa (ou pelo menos na frente dela), assim que você usar curingas locate
alterna a lógica e ancora a string de pesquisa no início e no final do material pesquisado.