First of all, I have limited knowledge about X Men Comics and that too is from watching the movies.
Is there any relation between the character of Victor Creed from X-Men Origins: Wolverine and Sabretooth from X-Men (2000)? And if yes, how come he ended up becoming a brainless henchman for Magneto?
IMO, he should have become arch enemy or nemesis of Wolverine.
Liev Schreiber who plays Victor Creed in X-Men Origins: Wolverine, is indeed essaying the role of Sabretooth (as depicted in X-Men).
From Wiki
Played by Tyler Mane, he was a henchman of Magneto in the first X-Men film and X-Men: The Official Game. Liev Schreiber plays him in the 2009 film X-Men Origins: Wolverine.
Since, your awareness of the comics universe is limited I'll stick to the movie for my explanation. To begin with, he is kind of an arch enemy to the Wolverine. Being his half-brother, he craves for his attention (in a negative way). And at the same time constantly tries (and succeeds) to physically better him to prove that he is more powerful.
Secondly, he only sides with Stryker (in X-Men Origins) as Stryker gives him the opportunity to hunt down Wolverine and make his life miserable. Also he expects that Stryker will transform him into Weapon XI aka Deadpool. But unfortunately, in X-Men he has been depicted as a mindless, growling beast.
Yes, they are the same person. Sabretooth (Victor Creed) and Wolverine (Logan) worked together for the CIA and they both were part of the Weapon X project.
How did he become brainless henchmen for Magneto?
In the comic he does not work for Magneto, with the exception of the time when Magneto becomes the leader of the X-men after the supposed death of Xavier. At one moment, Sabretooth was hired to kill Magneto but fails. Also, in the comic book, Sabretooth is very assertive and intelligent (he is an ex CIA) completely different to the brainless portrayals in the movies.
If you wonder how did he became evil and how his feud with Wolverine started, it is a long story but these are some key points:
Sabertooth's mutation is what causes him to become mindless.
As we see in Origins, Victor is very aggressive, to the point of mindless killing. Even when killing someone will lead to problems for him. This is how Logan and Victor end up facing a firing squad, before Stryker recruited them. And then, Logan continued to pull Sabertooth back from his more feral instincts until Logan walked away from a blood bath. Without Logan to remind him of his human side, his animalistic side continued to take over. It's represented by the changes in Victor, his nails grow longer into inhuman claws, he grows hairier, his voice is gruffer, he starts running on all four.
Four years of blood baths between being recruited and leaving Team X was enough to make Logan abandon Victor, after 125 years of fighting in wars together. Then 8 years later without Logan, Victor has no problem in hunting down children for experimentation, just so he can get "revenge". Now take another 20 years* of being without a conscience, of giving into his mutant animalistic side, we get the X-Men Sabretooth.
This is inline with Comic Sabretooth, as he's defined by his animalistic blood lust.
20 years of no one telling him not to bleach his hair blond too.
Although Origins is accurate in naming Sabretooth Victor Creed, it is inaccurate that he be declared Logan's brother. X Men Origins: Wolverine is based much on the comic book series Wolverine Origins. The entire opening scene is a spin of the comic series' events. However, they add that Victor's dad is actually James' (Logan) as well. In fact, in that story Creed isn't even around for these events.
So, the path in the film is a little off.
To answer your question a little more directly though. As Victor and Logan both work for Weapon X, they both have swiped memories. In the film, Logan loses his memory when he's shot in the head, this is just a creative addition to the original mythos. Although Sabretooth, in the comics rarely (if ever) worked with Magneto, I suppose in the first film, they were trying to portray him more beastly and less cunning as if his mind was swiped like logans.
In addition to other answers which are mostly based on comics, the below lines from Wikia imply that Sabretooth is indeed Victor Creed in the movie universe, too:
On their way, his truck is attacked Sabretooth (a further mutated Victor Creed). Logan tries to battle with him, but is knocked out. Before Sabretooth can do any further damage, he is stopped and chased away by Cyclops and Storm, who rescue both Logan and Rogue and bring them to the X-Mansion.
This page about Victor/SabreTooth confirms it's indeed the same person, further mutated, with lost memory:
About five years before the events of X-Men and X2: X-Men United: The Movie Prequel: Wolverine, he underwent Weapon X experimentation and was mutated into an even more bestial creature. He became bigger and stronger, and was much more feral in disposition. His mutation also erased his memory of his life prior to the point of the procedure. Additionally, he took on the name "Sabretooth".
After either being released by or escaping from Stryker, Sabretooth becomes a loner, gradually becoming unkempt in appearance. At some point just prior to X-Men, he associates himself with Magneto and joins him, Mystique and Toad in what would later become the Brotherhood of Mutants. Sabretooth's primary reason for joining was that Magneto promised to aid him in rediscovering his past life.
In the mainstream comics, Sabretooth and Magneto have not come together in any significant capacity. (Accept some non-mainstream comics such as House of M)
But in some media incarnations, Sabretooth was depicted as working under Magneto. Specially in the X-men Triology and Xmen: Evolution cartoon series etc. Sabretooth is one of the major characters of the X-men comics series so that may be the case to include him in X-men trilogy, but as a brainless henchman for Magneto is the director's/writer's choice.
X-men origins Wolverine is actually worked as a spin-off and has too many continuity issues. So relating characteristics of Victor Creed from X-men origins: Wolverine to X-men trilogy's Sabretooth is not a good idea. (Its a different factor that it is rumored that they will try to make them in same timeline (reference)).
relating characteristics of Victor Creed from X-men origins:Wolverine to X-men triology's Sabretooth is not a good idea. Moreover, I think your extended reference to the comics universe doesn't add any value to the answer, keeping in mind the question was about the movie franchise.