Consider the graph $G_k$ with vertex set $$\{u_1, \ldots, u_k, v_1, \ldots, v_k\}$$ and edges $$\{(u_1, v_1), \ldots, (u_1, v_k)\} \cup \{(u_2, v_1), \ldots, (u_k, v_{k-1})\} \cup \{(u_2, v_k), \ldots, (u_k, v_k)\}$$ It has $k$ perfect matchings, because once $u_1$ is assigned to $v_i$ this forces the assignments $$\{(u_2, v_1), \ldots, (u_i, v_{i-1}), (u_{i+1}, v_{i+1}), \ldots, (u_k, v_k)\}$$
Therefore a disjoint union of $G_p$ for all prime $p \le n$ has $n\#$ perfect matchings.
As noted in my earlier comment, this answers the question but disappoints you on all points of the motivation.
For a compact circuit representation similar to the encoding for the complete bipartite graph given in the question, encode both $u_i$ and $v_i$ from $G_p$ as $(p, i)$, so that the full input (the encoding of a $u$ vertex as $(p,i)$ and the encoding of a $v$ vertex as $(q,j)$) is $4 \lceil \lg n \rceil$ bits. Then the circuit needs to encode $$(p = q) \wedge (i = 1 \vee i = j \vee i = j+1)$$Addition of $1$ to a $\lg n$-bit number and equality testing of two $\lg n$-bit numbers can both be done in $O(\lg n)$ gates.
