Is there a single word or perhaps short phrase to express the feeling one gets when they meet someone amazing, say the love of their life, and wishes that they had met sooner? A cognate would be acceptable as well.
As far as I know, there isn't a word or expression in the English language that describes that specific phenomenon. I think that "Where have you been all my life?" is the most specific response to that particular situation, but it is more a rhetorical question than an expression. Sometimes people say "[they] found what [they've] been looking for", but that expression doesn't strictly apply to romantic interests, or even people.
The stereotypical thing to say is "where have you been all my life?"
Frustration? No. A feeling of having wasted part of your life? I don't think so.
When you meet someone amazing and you are madly in love, you don't think about that kind of stuff. You may even ask "How come I never met you before?" but you don't expect an answer.
REGRET / re·gret rəˈɡret /
verb 1. feel sad, repentant, or disappointed over (something that has happened or been done, especially a loss or missed opportunity). "she immediately regretted her words"
synonyms: be sorry about, feel contrite about, feel remorse about/for, be remorseful about, rue, repent (of), feel repentant about, be regretful at/about
noun regret; plural noun: regrets 1. a feeling of sadness, repentance, or disappointment over something that has happened or been done. "she expressed her regret at Virginia's death"
synonyms: remorse, sorrow, contrition, contriteness, repentance, penitence, guilt, compunction, remorsefulness, ruefulness. See Google regret
Regret, plain and simple. You regret you had not met them sooner. We're not supposed to regret our decisions in life because we're "Living in The Now" these days, but that has nothing to do with the meaning of the word.