Millennium - saw it on video, or possibly HBO, back in the early 90s and I remember it being really interesting but extremely strange and somewhat difficult to follow, but I was like 13 at the time so I’m guessing it would make much more sense were I to watch it today (hopefully).
Nothing new to add, but I’ve seen most of the movies mentioned here, and give high recommendations to Time After Time, The Time traveler’s Wife, and Frequency.
Oh, yeah, and the Doctor Who episode Blink. Yeah, it’s a TV show and not a movie, and the whole Doctor Who series is about time travel, but that particular episode plays around with cause-and-effect paradoxes especially well.
BTW, Orr,G., can I find La Jetée anywhere online? I haven’t seen that in over 35 years, and I’ve searched for it with no luck.
Army of Darkness - because it’s awesome.
Star Trek: First Contact - best of TNG films.
Donnie Darko - strange, mostly nonsensical movie about [nobody really knows], but I love it anyways.
Idiocracy - best documentary ever.
Men In Black 3 - actually my favorite of the MiB films.
About Time
British romantic dramedy film revolving around time travel where a young man tries to change his past to have a better future.
Frequency doesn’t seem to come up often in time travel discussions (perhaps because of the technicality that no one actually travels, except the slow way), but I find it a very well made and enjoyable example.
Also, it has the best description of time itself ever recorded. 
goonies
(ahem) the Planet of the Apes movies. The old ones.
Some titles I haven’t seen mentioned yet: (I only skimmed; I see some of these were mentioned.)
Primer - The standard in consistent time travel logic if you’re able to follow it. Will likely require several viewings plus internet research to grasp the totality of its vision. Extremely low budget. (Less than 20k.)
Triangle - Time travel plus horror, with a nice reveal at the end.
The I Inside - Anything with Sarah Polley in it is aces in my book.
Memento - Does it count as a time travel movie if only one character, plus we the audience through the eyes of that character, does any time traveling at all? Probably not. There is no time travel in the movie in any way, but it sure feels like it from our perspective.
The Jacket - Not the greatest movie, but I kind of dug it. And it’s legitimate time travel fiction.
Jacob Ladder - It’s not really a time travel story, unless you look at it sideways. Horror.
-
I saw the film at 20 and it didn’t make much sense either. For some reason, the scene where Cheryl Ladd is chain smoking while eating a salad has been stuck in my memory since then.
-
I just read the book this past weekend and it made less sense than the film. Cheryl Ladd’s character was (in the novel) f-ing a robot, and I believe the robot eventually became God to all the people who were time-napped. Or something.
http://vimeo.com/46620661 English dub version. I remember watching an English sub version, but this is the closest I found today.
Netflix has La Jetee.
I don’t remember much about Millenium but I also remember that scene.
Time After Time: a time-travelling H G Wells has to stop Jack the Ripper in late 70s America. Sounds rubbish from the premise, but a very good film.
Am I the only one who enjoyed Timeline?
I haven’t seen it yet but a friend recently recommended 2009’s Frequently Asked Questions About Time Travel to me.
Neither of these films are about time travel. Memento is a standard thriller with the story told in reverse, which dovetails nicely with the protagonist’s anterograde amnesia. Jacob’s Ladder is a horror film interspersed with Vietnam flashbacks, although by the end, it’s revealed that
the “flashbacks” are actually in Real Time, where Jacob Singer is slowly dying from combat injuries, whereas the “main story” represents his journey towards the afterlife.
But since we’re loosening up the definition of “time travel” here, I’ll add a couple more:
Donnie Darko: Hardly any time “travel” in this film, until it becomes clear that the time/space continuum’s been badly broken and somebody (Donnie, naturally) needs to “go back” and fix the problem.
The Butterfly Effect: Again, more of a “fix the space/time continuum” style of movie, but with many more hops back & forth in time. An excellent, underrated film; possibly Ashton Kutcher’s best role to date.
Run Lola Run: Another butterfly-effect story, where Lola must complete a certain task by a certain time – she fails, “reloads from a saved game”, tries and fails again, “reloads” and succeeds. Along the way, she meets random strangers whose personal destinies (as shown via a montage of Polaroid snapshots) become dramatically different due to tiny alterations in each time-stream. It’s actually more like an 80-minute techno video – but if you enjoy watching Franka Potente work up a sweat in a red wig while wearing a skimpy pale blue tank top, this movie earns my full recommendation. 
Run Lola Run is an excellent film, and does fit the “feel” of the time travel genre if not technically qualifying. Regarding your description, I viewed it as more of a quantum story told in three different universes.
I saw it and enjoyed it, but it’s now been a few years and I remember almost nothing about it. I’ll watch anything with Anna Faris, so for all I know it was terrible, but I do remember enjoying the film.
I’ve always been a sucker for Peggy Sue Got Married.
The only one I can think of that hasn’t been mentioned is Deja Vu, with Denzel Washington.
But where oh where is Time Cop?