Можно не хранить все анаграммы в одном массиве: сделали перестановку, проверили в базе слов, затем следующую перестановку. Это избавит от OutOfMemory проблемы. Но прибавит немного времени, так как будут повторения.
Затем можно разбить базу слов на 28 отдельных баз, где хранятся слова только определённой длинны. Должно немного ускорить поиск.
А вот как сделать быстрее - я бы использовал другой язык программирования (Go, C, Java) и попытался бы распараллелить процесс на потоки.