I believe the movie you are thinking of is Knights, circa 1993. From the Wikipedia page:
The cyborg Gabriel (Kris Kristofferson) was created to destroy all other cyborgs. He later rescues Nea (Kathy Long) by killing Simon (Scott Paulin), one of the other cyborgs. Gabriel trains Nea to become a cyborg killer and help him. They continue to kill cyborgs until Gabriel is torn in half by one of his targets and taken to the cyborg camp. Nea follows Jacob and challenges the cyborg leader Job (Lance Henriksen) to a fight. She ends up killing most of the cyborgs in the camp.
She finds Gabriel and straps him to her back. Together, they battle the cyborgs until Gabriel has her put him down so he can attach a dead cyborg's legs to himself. They then pursue a fleeing Job, but before they can catch him the Master Builder captures Nea's brother, taking him to Cyborg City. Meanwhile, Gabriel is battling Job and hits him in the face, causing it to explode. Job tells Gabriel that the cyborg population can't be stopped. Job dies moments later. Gabriel and Nea ride off into the sunset, in search of her brother and Cyborg CityCleaned.
Side note: At first I thought your movie was Circuitry Man, since it also has a woman and robot traveling around in a post apocalyptic world.