I don't think there is an answer for this because part of the problem reduces to an open problem.
Let $\mathcal{N}_n(p)$ be the number of path of length $p$ (more precisely, covered $p$ squares) on a $n\times n$ grid. As mentioned in comment, we can compute some of these $\mathcal{N}_n(p)$ by brute force.
$$\begin{array}{r|rr} & \rlap{\quad\quad\quad\quad\quad\quad n}\\ p & 4 & 5 & 6 & 7 & 8\\ \hline 1 & 16 & 25 & 36 & 49 & 64\\ 2 & 84 & 144 & 220 & 312 & 420\\ 3 & 408 & 768 & 1240 & 1824 & 2520\\ 4 & 1764 & 3768 & 6508 & 9984 & 14196\\ 5 & 6712 & 17280 & 32520 & 52432 & 77016\\ 6 & 22672 & 74072 & 156484 & 268048 & 408764\\ 7 & 68272 & 296390 & 722384\\ 8 & 183472 & 1110000 & 3193800\\ 9 & 436984\\ 10 & 905776\\ \end{array}$$
Based on these numbers, an OEIS search return the series A186861 - T(n,k) - Number of n-step king's tours on a kXk board. It mentions there is an empirical formula for $T(n,k)$ for large $n$:
$$T(n,k) = 3T(n-1,k) - 3T(n-2,k) + T(n-3,k)\quad\text{ for large } n$$
I look back at my program computing $\mathcal{N}_n(p)$, I find the empirical formula is true.
Imagine we have an $\infty \times \infty$ grid and $p$ any positive integer.
Let $X_p$ be the collection of self avoiding path covered $p$ squares starting at origin.
Given any path $\ell \in X_p$, let $(x_1,y_1) = (0,0)$, $(x_2,y_2), \ldots, (x_p,y_p)$ be the squares visited by $\ell$.
Let $W(\ell)$ and $H(\ell)$ be the horizontal and vertical span of the path. More precisely, $$\begin{align} W(\ell) &= \max\{ x_k : 1 \le k \le p \} - \min\{ x_k : 1 \le k \le p \}\\ H(\ell) &= \max\{ y_k : 1 \le k \le p \} - \min\{ y_k : 1 \le k \le p \} \end{align}$$
To generate all possible paths on a $n\times n$ grid, we can walk through the set of path in $X_p$ and translate each of them on the $n \times n$ grid. Given any $\ell \in X_p$, the number of paths it can generate is
$$\begin{cases}(n - W(\ell))(n - H(\ell)),& n \ge \max( W(\ell), H(\ell) )\\ 0,&\text{otherwise}\end{cases}$$ As a result,
$$\mathcal{N}_n(p) = \sum_{\substack{ \ell\in X_p\\ n \ge \max( W(\ell), H(\ell) )} } (n-W(\ell))(n-H(\ell))$$
When $n \ge p$, we find $n \ge W(\ell)$ and $\ge H(\ell)$ for all $\ell \in X_p$. This leads to
$$\bbox[12pt,border: 1px solid blue;]{ \mathcal{N}_n(p) = \sum_{\ell\in X_p } (n-W(\ell))(n-H(\ell)) = \alpha_p n^2 - \beta_p n + \gamma_p \quad\text{ whenever } n \ge p } $$ where $$ \begin{cases} \alpha_p &= |X_p| = \sum\limits_{\ell \in X_p} 1\\ \beta_p &= \sum\limits_{\ell \in X_p} (W(\ell) + H(\ell))\\ \gamma_p &= \sum\limits_{\ell \in X_p} W(\ell) H(\ell) \end{cases} $$ In such case, $\mathcal{N}_n(p)$ becomes a quadratic polynomial in $n$ and the empirical formula is justified.
Following are some numbers for small $p$. $$\begin{array}{r|rrr} p & \alpha_p & \beta_p & \gamma_p\\ \hline 1 & 1 & 0 & 0\\ 2 & 8 & 12 & 4\\ 3 & 56 & 144 & 88\\ 4 & 368 & 1308 & 1108\\ 5 & 2336 & 10456 & 11160\\ 6 & 14576 & 77924 & 99292\\ 7 & 89928 & 555464 & 817760\\ 8 & 550504 & 3839372 & 6382124\\ \end{array}$$
I have tried to use this number to make an OEIS search but I cannot find anything.
In any event, it is clear the leading behavior of $\mathcal{N}_n(p)$ is controlled by the number $\alpha_p$. Numbers like $\alpha_p$ has been studied before in mathematics, statistical physics and chemsitry. It is usually under the subject Self Avoiding walk. If is also clear if we have a general formula for $\mathcal{N}_n(p)$, we will have a formula for $\alpha_p$. Unluckily, finding a formula for $\alpha_p$ is an open problem!
Quoting wiki:
There is currently no known formula for determining the number of self-avoiding walks, although there are rigorous methods for approximating them. Finding the number of such paths is conjectured to be an NP-hard problem.
My recommendation is this:
If you want to proceed mathematically, you should forget this version of problem first. You should look up the literature of self-avoiding walks for a simpler walk. For example, a walk only allow moves in horizontal and vertical direction on an infinite square lattice. Learn the basic first and see what sort of techniques are available for the simpler case.
