How does this generate a permutation?
It is a permutation not in the sense that it permutes the bit positions of the given input, but in the sense that it is a one-to-one correspondence from a set (of bitstrings) to the same set, as defined in that paper:

2. Terminology …
Let $F^n$ be the set of all ${2^n}^{2^n}$ functions mapping
$\{0,1\}^n$ into $\{0,1\}^n$… Let $P^n\subset F^n$ be the set of such
functions that are permutations, i.e., they are 1-1 onto functions.