再起嫌いだわ
難しいことせず素直に書くならこうかな

static IEnumerable<string> AAAToZZZ(int n)
{
if (n < 0) throw new IndexOutOfRangeException();

IEnumerable<string> result = AToZ();
for(i = 1; i < n; i++)
result = Hoge(result, AToZ());

return result;
}

static IEnumerable<string> Hoge(IEnumerable<string> items1, IEnumerable<string> items2)
{
// items1+items2の組み合わせ
foreach (var item1 in items1)
foreach (var item2 in items2))
yield return item1 + item2;
}