at which point it returns [[1],[2],[3]] to the previous level of recursion.

Important distinction: it returns ([1],[2],[3]), a list of three arrayref, not an arrayref to an array of three arrayrefs.

So the outer map body is executed three times, first with $_ aliased to [1], then to [2], then to [3]. The inner map is run over (4,5,6) each of the three times, and returns, respectively, ([1, 4], [1, 5], [1, 6]), then ([2, 4], [2, 5], [2, 6]), then ([3, 4], [3, 5], [3, 6]), so the next-to-last recursive call returns ([1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4], [3, 5], [3, 6]).

Hope this gets you further on.