I found the movie. I think I was off on the time travel part, I'll have to rewatch it, but it's called My Girlfriend is a Cyborg, Cyborg She, released in 2008.
It is 22 November 2007. Jiro Kitamura (Keisuke Koide) is spending his 20th birthday alone. As he buys a birthday present for himself in a shopping mall, he gets the attention of a 'cute girl' (Haruka Ayase) and she surprisingly smiles at him. Afterwards, she successfully steals a pair of clothes, which Jiro notices, but he ignores it as she walks away in front of him and he is distracted by her beauty. The mystery girl, who seems to be interested in him, follows him to a restaurant, where he eats spaghetti on the advice of his grandmother (later revealed to be his mother who gave birth to him in old age) for a longer and peaceful life. She suddenly appears and sits with him, stating that it's 'her birthday too'. The two of them then exchange birthday presents. The girl, who seems unused to everything, behaves very boldly and suddenly rushes with Jiro out of the restaurant without paying the bill, provoking the manager to chase the two through Tokyo. As he spends time with the girl, Jiro finds himself charmed by her. But, after a few hours, the girl insists she has to leave and goes with a tearful goodbye.
The story then jumps to one year later, as Jiro again celebrates his birthday alone in the same restaurant. All of a sudden, the same-looking girl appears in front of him. Jiro's older self from 65 years in the future had sent this girl to save him from a disastrous fate. She was actually a cyborg, modelled after the girl he met a year before in 2007. While he rejoices in her presence, the restaurant is suddenly attacked by a gunman, but she saves him and the other guests by throwing the gunman out of the window. Despite her 'cute' outward appearance, she is incredibly strong and behaves erratically. Later, in Jiro's home, she reveals her true identity by showing him a 3D projection of a video in which an elderly Jiro from the future warns him about an upcoming disaster. The old Jiro told him that the shooting at the restaurant paralyzed him for life. However, a lottery ticket he bought earlier was fortunate for him. He spent all his time and money on one thing: creating the cyborg girl to save his past self about 60 years ago. Now, he has recreated the history of his timeline by sending her. This was not supposed to happen, but things would correct themselves by recalibrating to the right dimension. In a short span of time, she becomes Jiro's protector as well as a loyal friend and they both share some wonderful moments. She also saves many other lives from tragic deaths that old Jiro had regretted witnessing.
Over time, Jiro not only becomes dependent on, but also falls in love with her. However, when she cannot return his feelings, he gets irritated and forbids her from seeing him unless she can do so. He begins to regret this, especially when it becomes apparent that she is still helping him while staying out of his sight. Another disaster soon occurs: a gigantic earthquake completely devastates Tokyo. As his apartment block collapses, she appears to help him, but even her superhuman strength isn't enough to save him. After telling Jiro that she now understands his feelings, she is destroyed while saving him. Later, distraught, Jiro finds her body and spends the next 61 years trying to rebuild her. He eventually succeeds but dies shortly after.
Further in the future (63 years later) in 2133, a girl is told by her friend that there is a cyborg on display that looks just like her. She is curious, and buys the now defunct cyborg to experience the memories stored in her hard-drive. Intrigued, she then decides to fulfil her wish of going back in time to meet Jiro. She is revealed to be the actual girl who met Jiro on his 20th birthday (November 22, 2007), who did so because she wanted to meet him before the cyborg did. After the events of the story, she comes again to the moment when Jiro weeps over the destroyed body of the cyborg. She then says "I can feel his heart," and decides to live with Jiro from then on, changing his fate again.