Though I don't honestly understand your comment about linear/memoisation vs exponential. Zipwith is basically talk recursive, so linear time and tail is constant?
The reason the first version is exponential (in most languages, including Haskell) is that it evaluates "fib n" repeatedly. If you save the results (memoize) so that you only evaluate "fib n" once for each "n" then becomes linear (assuming the memoization itself is constant-time). The second version does this by arranging the results into the list "fibs" where the n-th element of the list is "fib n". In the expression "1 : 1 : zipWith (+) fibs (tail fibs)", the result of "zipWith" starts at index n = 2 while "fibs" starts at index n = 0 and "tail fibs" starts at index n = 1, so this is equivalent to "fibs !! 0 = 1; fibs !! 1 = 1; fibs !! n = (fibs !! n - 2) + (fibs !! n - 1)"—just as in the first version. The difference is that each result is kept in the list once it's been computed and not re-evaluated each time it's referenced, so the number of additions is linear with respect to "n".
Going into a bit more detail, since Haskell uses lazy evaluation at first the list just consists of thunks (unevaluated expressions). (This technically includes the "next" or "tail" pointers as well as the list elements, which is why we can define "fibs" as an infinite list, but I'll ignore that for now.) When you evaluate "fibs !! n" it first evaluates "fibs !! n - 2" and "fibs !! n - 1", adds them, and then mutates the list entry to store the evaluated result in place of the original thunk. Of course the recursive calls also store their results before returning, so when "fibs !! n - 1" needs "fibs !! n - 2" that result is already available and doesn't need to be reevaluated. (Note that I'm just using "fibs !! n" as shorthand for "the n-th element of fibs" here; we don't actually walk the list from the start each time. We step through the output of zipWith once, and zipWith steps through its inputs "fibs" and "tail fibs" once each in parallel, making this part linear-time.)
The scope of "fibs" here is a particular call to "fib n" so it can be garbage-collected once we have our result. If you moved the definition of "fibs" to the top level then it would avoid re-evaluation across multiple calls, at the cost of keeping the evaluated part of the list in memory for the duration of the program.
You could also use an array instead of a list, since there is a known upper bound on the number of elements needed for a given "n"; this would be more typical of the "dynamic programming" approach to memoization, but in Haskell it's a bit longer, and with list fusion optimizations the array isn't necessarily more efficient. The result would look like:
fib n = fib' n
__where
____fib' 0 = 1
____fib' 1 = 1
____fib' m = (fibs ! (m - 2)) + (fibs ! (m - 1))
____fibs = listArray (0, n - 1) (map fib' [0..])
Where fib' looks a lot like the first recursive definition, except that it refers to the array rather than calling itself directly. (But keep in mind that "fibs ! n" is just a particular instance of "fib' n", so it's still recursive. The difference is that the result is stored in the array and not discarded.)
This can easily be generalized for any recursive function with a parameter suited for use as an array index:
memoize :: Ix i => (i, i) -> ((i -> a) -> i -> a) -> i -> a
memoize bounds f = let arr = listArray bounds (map (f (arr !)) (range bounds)) in (arr !)
-- abstract out the recursive calls
fib fib' 0 = 1
fib fib' 1 = 1
fib fib' n = fib' (n - 2) + fib' (n - 1)
naiveFib n = fix fib n
memoizedFib n = memoize (0, n) fib n
Which can then be used as the basis for all kinds of dynamic programming solutions.