Se um dos arquivos pode ser carregado em memória, carregue-o num Set, ao invés de uma lista, e compare o segundo arquivo usando o contains do set.
Como o contains do set tem performance de O(1), vai ficar extremamente rápido. Além disso, o set eliminará frases duplicadas, que só atrapalhariam a performance da sua comparação.
PS: Como seu arquivo são Strings, vale a pena tambem testar a diferença entre um HashSet e um TreeSet. Creio que o segundo deva inclusive apresentar performance superior ao primeiro, pela natureza ordenada do alfabeto.