Корутина не поможет, т.к. она всё равно выполняется в основном потоке Unity, многопоточности не будет, как таковой.
Да, используйте Thread'ы, они отлично работают в Юнити, если их правильно применять. Как с тредами работать - уроки и документация есть в гугле.
Дальше разбивайте массив на Х частей, запускайте Х циклов, по одному на каждую часть, и сохраняйте Х листов.
После пройдетесь по листам и организуете результаты в нужном порядке.