To amplify on Christian's answer, the problem on a $K \times N$ grid for fixed $K$ and varying $N$ admits a finite-state transition model, so in particular is given by a linear recurrence.
The key is to find the right set of states. If you take an edge-disjoint path on a $K \times N$ grid and slice it on a vertical line through the middle passing through a set of horizontal edges, you'll see the path crossing along some odd number of these edges ($\le K$). On both the left and right we'll see a collection of paths with these endpoints. There's another constraint, that we end up with a single, connected path without disjoint loops; to take that in to account, also record a matching: which endpoints are paired up on the right hand side. All but one of the endpoints are paired up in this way. (You could also choose the left, and end up with a slightly different matrix.)
For instance, in the $3 \times N$ case, there are $6$ states. If we record an occupied edge by $\times$ and an unoccupied edge by $\circ$ and turn everything on its side, the states are
$$
\times\circ\circ\quad\circ\times\circ\quad\circ\circ\times\quad\times_1\times_1\times
\quad\times_1\times\times_1\quad\times\times_1\times_1
$$
where the subscript indicates the matching. (In this case, there is at most one matched pair.)
Next consider the transitions. If you consider two adjacent vertical slicings of a path, you'll see two possibly different states. The set of edges that are occupied in the middle is determined by which edges are occupied in the two different states. There is sometimes a choice about how the strands are connected up. However, some of these choices will be ruled out by the constraints on the connectivity; usually you will end up with just $0$ or $1$ possibilities.
For instance, in the $3 \times N$ case, with the states in the order above, I get the following matrix of possibilities:
$$
M =\begin{pmatrix}
1 & 1 & 1 & 1 & 1 & 0 \\
1 & 1 & 1 & 1 & 0 & 1\\
1 & 1 & 1 & 0 & 1 & 1\\
0 & 1 & 1 & 1 & 0 & 0\\
0 & 1 & 0 & 0 & 1 & 0\\
1 & 1 & 0 & 0 & 0 & 1
\end{pmatrix}
$$
For the ultimate answer, you want to look at paths that start at the upper-left and go to the lower-right. You can incorporate that nicely by adding an extra slice to the left of the entire diagram, with only the top slot occupied, and another to the right of the diagram, with only tho lower slot occupied.
Concretely, in the $3 \times N$ case, the number of paths is given by the $(1,3)$ entry of $M^N$.
For the $4 \times N$ case, you would get a $16 \times 16$ matrix, which is straightforward but somewhat tedious to work out. As a result, the answer will satisfy a linear recurrence of order $16$.
An interesting variation is to consider only crossingless paths. In this case, the matching must be crossingless, so we only get 5 states in the $3 \times N$ case and $12$ in the $4 \times N$ case.
Update Jan 7: The matrix above is wrong: it should be
$$
M =\begin{pmatrix}
1 & 1 & 1 & 1 & 1 & 0 \\
1 & 1 & 1 & 2 & 2 & 2\\
1 & 1 & 1 & 0 & 1 & 1\\
0 & 1 & 1 & 1 & 0 & 0\\
0 & 1 & 0 & 0 & 1 & 0\\
1 & 1 & 0 & 0 & 0 & 1
\end{pmatrix}
$$
Update 2: And here's an image illustrating what is actually being counted:
I permuted the entries slightly, but they're labelled along the sides. The dotted paths are there to help in the counting: the non-allowed configurations would form a closed loop.
Here is an answer to 1. It is known that for any $A > 0$ that $\sum_{m \leq x} \mu(m) e(\alpha m) = O_A(x (\log{x})^{-A})$ uniformly in $\alpha$. For instance, consult Theorem 13.10 of Iwaniec and Kowalski's book, Analytic Number Theory. This uniform bound comes from combining the zero free region of Dirichlet L-functions with Vinogradov's method. This bound shows that $|\hat{\mu}(k)| \leq C_A (\log{n})^{-A}$.
This gives 2) for $A$ fixed. Edit 1: It gives 3) also.
Edit 2: I would guess the truth is $|\hat{\mu}(k)| \leq C(\varepsilon) n^{-1/2 + \varepsilon}$ so $s$ would have to be almost as large as $n$ to get anything not $o(1)$.
Best Answer
OK, it seems that a probabilistic swapping argument works (and is simpler than the two other suggestions I made above).
Firstly, by the Bourgain-Sarnak-Ziegler criterion (Proposition 1 in http://terrytao.wordpress.com/2011/11/21/the-bourgain-sarnak-ziegler-orthogonality-criterion/ ), it suffices to show that
$$ \sum_{n \leq x} WS(pn) WS(qn) = o(x)$$
for all fixed distinct primes $p$, $q$, and in the limit $x \to \infty$.
Fix $p,q,x$. We phrase things probabilistically. Let $n$ be a random integer between $1$ and $x$; the objective is to show that
$$ {\bf E} WS(pn) WS(qn) = o(1) \quad\quad (1).$$
The way we will do this is to construct a new random variable $n'$, coupled with $n$, which asymptotically almost surely (i.e. with probability $1-o(1)$) is such that $$ WS(pn) WS(qn) = - WS(pn') WS(qn') \quad\quad (2) $$ aas. Also, the total variation distance between the distribution of $n$ and the distribution of $n'$ will be established to be $o(1)$, so that $$ {\bf E} WS(pn) WS(qn) = {\bf E} WS(pn') WS(qn') + o(1).$$ Putting these facts together will give the claim (1).
It remains to construct $n'$ with the desired properties. For simplicity let us begin with the case when $WS(p) = -WS(q)$. Then to obtain $n'$ from $n$, what one does is scan the binary expansion of $n$ for a block of zeroes of length at least $\ell := 10 \max( \log_2 p, \log_2 q ) + 11$ (say); note from the law of large numbers that there are going to be about $2^{-\ell} \log_2 x$ such blocks aas. We randomly select one of these blocks, and flip the middle zero in this block to a one to create $n'$. A bit of thought (using the long multiplication algorithm) shows that $WS(pn') = WS(pn) WS(p)$ and $WS(qn') = WS(qn) WS(q)$, giving (2) since $WS(p) = -WS(q)$. A rather tedious double counting involving the Chernoff inequality (which I will omit here) also shows that the distribution of n' is within o(1) in total variation to that of n, giving the claim. (The point is that the indegrees and outdegrees of the edit graph connecting potential $n$s to potential $n'$s both concentrate around the same quantity, namely $2^{-\ell} \log_2 x$.)
Of course, it could happen that $WS(p)=WS(q)$ instead. But a variant of the above argument will work as long as one can find at least one natural number $a$ for which $WS(ap) = -WS(aq)$, basically one has to insert in the binary expansion of $a$ in the middle of a sufficiently large block of zeroes of $n$ to make $n$, rather than flipping a single bit. So the only way things can go wrong is if the primes $p,q$ are such that $WS(ap)=WS(aq)$ for all natural numbers $a$ (i.e. if there is absolutely no cancellation at all in $\sum_{n \leq x} WS(pn) WS(qn)$. This can be eliminated as follows. Without loss of generality we have $p > q$ and $p$ odd. Then we can find $n,k$ such that $qn < 2^k < pn < 2^{k+1}$. We observe that
$$ WS(p (n+2^{k+1}) ) = - WS(pn) WS(p)$$
and
$$ WS(q (n+2^{k+1}) ) = WS(qn) WS(q)$$
and so we cannot have $WS(ap)=WS(aq)$ for all $a$.