Al final me ha funcionado.
He añadido "<base href="http://tudominio.algo/shop/" />" justo despues de la etiqueta de apertura del head, y en el htaccess he puesto lo siguiente:
Código Apache:
Ver originalRewriteEngine on
RewriteBase /shop
RewriteRule ^categoria/(.*)/?$ index.php?categoria=$1 [L]
Supongo que lo que me faltaba era indicar la ruta base en la cabecera.
Muchas gracias!