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:
![Matrix of edge disjoint paths][1]
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.

  [1]: http://img137.imageshack.us/img137/3460/edgedisjointmatrix.png