Teste --regex (sem um 'p') em vez de -r (também conhecido como --regexp ). Isso diz a locate para usar regexps estendidos em vez de básicos.
locate --regex "^/var/lib/tomcat[0-9]{1,2}/" -l 10
alternativamente, escape de { e } com \ para torná-los especiais na regex básica.