This is a variation of the problem of enumerating self avoiding walks. In general there are no closed form expressions for the number of self avoiding walks between two arbitrary points in a grid of arbitrary dimension; although I have not seen the problem considered with the particular constraints in question, I would be surprised if there was a closed form solution in this case. However, reliable approximation methods do exist for such enumeration problems, and such an approximation may be suitable for your purposes.
Edit: Using a rather naive approach, I've worked out the following lower bound for the number of self-avoiding walks on an $n\times m$ rectangular grid from a given boundary point to a given interior point. With more mathematical sophistication, it is likely that significant improvements could be made on this bound.
Let $A$ be an $n\times m$ rectangular grid, with $n>2$ and $m>2$. That is, let $A$ be the collection of integer points in an $xy$ cartesian plane satisfying the conditions $0 \leq x \leq n$ and $0 \leq y \leq m$. Let $\left(a,b\right)$ be a point in the interior of $A$. In the wikipedia article it discusses the case of walks from one diagonal to another with moves only in the positive direction. I shall call such walks positive walks. There is a simple formula for the number of positive walks from one point to another in a rectangular grid.
We claim that the number of self-avoiding walks from a given point on the boundary to $\left(a,b\right)$ is bounded below, independently of the choice of the point on the boundary by
$$ \binom{a+b}{b} + \binom{a+m-b}{m-b} + \binom{n-a+b}{b} + \binom{n-a+m-b}{m-b}$$
That is, by the number of positive walks from any of the four corners of the grid to the point $\left(a,b\right)$.
Let $\alpha$ be a point on the boundary of $A$. We first bound the number of self-avoiding walks from $\alpha$ to $\left(a,b\right)$ below by the number of positive walks from any point on the boundary of an $\left(n-2\right)\times\left(m-2\right)$ rectangular grid $B$ to the point $\left(a-1,b-1\right)$ within $B$. Our requirement that $n>2$ and $m>2$ is to allow this step to work with a minimum of headache. There is probably an exact solution in the case where $n \leq 2$ or $m \leq 2$.
We may consider those walks which first move $k$ steps in the counter-clockwise direction around the boundary, then move one step into the interior, and whose successive moves follow a positive walk directly to $\left(a,b\right)$. We may do this for $k$ from 0 to $2n+2m-1$, excluding those values of $k$ which place the walker upon a corner, where there is no move into the interior. It is clear that we have produced a disjoint collection of self-avoiding walks equal in number to the number of positive walks from the boundary of an $\left(n-2\right)\times\left(m-2\right)$ $B$ to the point $\left(a-1,b-1\right)$ in $B$.
Now we use the result that the number of positive walks from one diagonal to another on an $j\times k$ grid equals
$$\binom{j+k}{j} = \binom{j+k}{j,k} = \binom{j+k}{k} $$
Using this result, we may express the number of positive walks from any point on the boundary of $B$ to the point $\left(a-1,b-1\right)$ as the sum
$$\sum_{i=0}^{b-1}\binom{a-1+i}{a-1} + \sum_{i=0}^{m-b-1}\binom{a-1+i}{a-1} + \sum_{i=0}^{b-1}\binom{n-a-1+i}{n-a-1} + $$
$$\sum_{i=0}^{m-b-1}\binom{n-a-1+i}{n-a-1} + \sum_{i=0}^{a-1}\binom{b-1+i}{b-1} + \sum_{i=0}^{n-a-1}\binom{b-1+i}{b-1} + $$
$$ \sum_{i=0}^{a-1}\binom{m-b-1+i}{m-b-1} + \sum_{i=0}^{n-a-1}\binom{m-b-1+i}{m-b-1} - 4$$
Where we subtract 4 because the above expression involving binomial coefficients counts each straight line path from the boundary of $B$ to $\left(a-1,b-1\right)$ twice. Since we have specified that $n>2$ and $m>2$, we may safely ignore this 4 by adding in some walks that first move $k$ steps in the clock-wise direction, move away from the boundary, and then follow a positive walk to the finish point.
Using the well known binomial coefficient identity
$$ \sum_{i=0}^{k}\binom{r+i}{r} = \binom{r+k+1}{r+1}$$
We may express the above sum, without the addition of the constant $-4$, as
$$\binom{a+b-1}{a}+\binom{a-1+m-b}{a}+\binom{n-a-1+b}{n-a}+\binom{n-a-1+m-b}{n-a} + $$
$$\binom{b-1+a}{b}+\binom{b-1+n-a}{b}+\binom{m-b-1+a}{m-b}+\binom{m-b-1+n-a}{m-b}$$
After some simple manipulations, we may pair up the terms and combine each pair using the identity $\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$ to get
$$ \binom{a+b}{b} + \binom{a+m-b}{m-b} + \binom{n-a+b}{b} + \binom{n-a+m-b}{m-b}$$
The result we were attempting to prove.
I'm not sure how useful this result is, but I thought it was interesting how easily things lined up to be simplified by standard binomial coefficient identities. I also thought it was interesting how the final formula has a straightforward combinatorial interpretation.
Best Answer
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:
My recommendation is this: