My understanding is that:
1) given a graph G with n vertices and m edges, DFS is O(n + m)
2) DFS can be used to produce a list of all simple paths between 2 vertices u and v
This would mean that DFS can produce a list of all simple paths between u and v in polynomial time.
However, if we could could list all simple paths between u and v in polynomial time, we should be able to decide if G has a Hamilton Path between u and v in polynomial time.
Since determining if G has a Hamilton Path is NP-Complete, my understanding must be incorrect. I'm hoping someone can clarify what I'm missing?
What you're missing is that there could be an exponential number of paths that stop short of connecting $u$ and $v$. Discovering these dead ends using depth-first search and backtracking is what makes DFS require worst-case exponential time to find a Hamiltonian path.