Coisas que podem fazer com que uma exclusão seja lenta:

• excluindo muitos registros
• muitos índices
• indices ausentes em chaves estrangeiras em tabelas filhas. (obrigado a @CesarAlvaradoDiaz por mencionar isso nos comentários)
• impasses e bloqueios
• gatilhos
• exclusão em cascata (os dez registros pai que você está excluindo podem significar a exclusão de milhões de registros filho)
• Registro de transações precisando crescer
• Muitas chaves estrangeiras para verificar

Portanto, suas opções são descobrir o que está bloqueando e corrigi-lo ou executar as exclusões fora do horário comercial, quando elas não estiverem interferindo na carga normal de produção. Você pode executar a exclusão em lotes (útil se você tiver gatilhos, exclusão em cascata ou um grande número de registros). Você pode descartar e recriar os índices (melhor se você também puder fazer isso fora do horário comercial).