Let $p_n$ denote the total number of paths between $u$ and $v$ through some $w$. Your path can have anywhere between $3$ and $n$ vertices. If your path has $k$ vertices, then there are $k-3$ choices of intermediate vertices from the $n-3$ free vertices together with $(k-2)!$ choices of rearrangements. Therefore in total we have
$$p_n=\sum_{k=3}^n\binom{n-3}{k-3}(k-2)! = \sum_{k=3}^n\frac{(n-3)!}{(n-k)!}(k-2)$$
This is essentially the formula, but there is a "closed form" in terms of the incomplete gamma function if you want.
We rewrite the sum with $\ell = n-k$ as
$$p_n=(n-3)!\sum_{\ell=0}^{n-3}\frac{n-\ell-2}{\ell!}=(n-2)!\sum_{\ell=0}^{n-3}\frac{1}{\ell!}-(n-3)!\sum_{\ell=0}^{n-4}\frac{1}{\ell!}$$
Each of the summands can be expressed in terms of the incomplete gamma function, namely
$$k!\sum_{\ell=0}^{k-1}\frac{1}{\ell!} = ek\Gamma(k,\ 1)=ek(k-1)\Gamma(k-1,\ 1) + k$$
where $e$ is the base of the natural logarithm and $\Gamma(k,\ 1)$ is the incomplete gamma function. Using the above, we can simplify as
$$\begin{align}p_n &= e(n-2)\Gamma(n-2,\ 1)-e(n-3)\Gamma(n-3,\ 1)
\\&=e(n-2)(n-3)\Gamma(n-3,\ 1)-e(n-3)\Gamma(n-3,\ 1) + n-2
\\&=e(n-3)^2\Gamma(n-3,\ 1)+n-2\end{align}$$
The sequence begins from $n=3$ as
$$1,\ 3,\ 11,\ 49,\ 261,\ 1631,\ \cdots$$
This looks a lot like the way you determine the chromatic polynomial,
but in a some sense "reversed": you know the values of your most "complicated" graphs
instead of iterating until you have reached the simplest ones.
Consider one edge $e$, then the number of hamiltonian cycles in
$G$ equals the number of cycles in $G-e$ (those that do NOT use the edge)
plus the number of cycles in $G/e$ (those that DO use the edge).
This can be transformed into a recursive algorithm: you know the values for
the complete graphs, and all other intermediate values you require
are the result of removing a smaller list of edges from a smaller complete graph.
However this will not perform at all on anything but the smallest examples
and it certainly will not give you anything like a closed formula for the number
of hamiltonian cycles. I am not at all sure if this is an acceptable solution.
EDITED AFTER REQUEST FOR DETAILS:
Consider next pseudocode.
int function h(int n, List l)
{
if (l is empty) { return number of hamilton cycles in K_n }
create new list lNew;
return h(n, l minus last element) - h(n - 1, lNew);
}
This function $h$ calculates the number of hamiltonian cycles in $K_n$
when the edges of the list $l$ are missing.
You use the recurrence $h(G-e)=h(G)-h(G/e)$, so you repeatedly put
one edge back into the graph until you have put back everything.
You have to decide on how to represent the edges on the list.
One option is to represent each edge on $l$ simply as a pair of numbers in the range $1..n$.
The only tricky part is the creation of the list $lNew$.
You cannot just copy its elements from the list $l$, since
they refer to edges of a $K_{n-1}$ after the recursion, so depending on the edge you are removing
you need to manipulate the list elements.
I have no clue how this will perform with the numbers you mention. The most important thing will be that the list of edges is not too long, since that will determine the depth of the recursion. Be sure to use some kind of 'big integer' arithmetic or find other ways to avoid large numbers.
Best Answer
You can just count them based on length. For now, we will ignore that the reverse of a path is the same path.
There are $n(n-1)(n-2)$ paths of length 2.
...
There are $n!$ paths of length $n-1$.
So, remembering that we have double-counted, the total number of paths in $K_n$ is $$\frac12\sum_{k=0}^{n-2}\frac{n!}{k!}=\frac{n!}2\sum_{k=0}^{n-2}\frac1{k!}\approx\frac{en!}{2}$$ where the approximation should be pretty good for large $n$.