The prophecy doesn't merely say "he will mark him", it says
and the Dark Lord will mark him as his equal
When talking about the prophecy, Dumbledore says
"Voldemort himself would mark him as his equal... He chose you, not Neville. He gave you the scar" (OotP)
So Dumbledore says that Voldemort marked Harry as his equal with the scar, and later Harry repeats this when talking to his friends.
There are several meanings of the work "mark", here quoted from the Cambridge dictionary. Of those, these apply here:
There is the meaning damage or make dirty
Make sure you don't mark the walls while you're moving the furniture around.
This meaning would cover the scar as a mark left by Voldemort, if the prophecy would just say "he will mark him".
There is the meaning indicate
I've marked the route around the town's one-way system on the map.
This is the meaning that would fit the part "will mark him as his equal". It implies that the mark is not left by accident or negligence, but that there is the intention to create the mark and for the mark to have a specific meaning.
That means for "the Dark Lord will mark him as his equal" to be true, it is necessary that
- Voldemort considered Harry his equal
- Voldemort intended to leave a symbol on Harry that shows that he is his equal.
To address these points
Harry is just a baby, so it is unlikely that Voldemort would consider him his equal. He considers Harry to have the potential to become a danger later, and therefor decides to kill him before that can happen, but that doesn't mean he fears him as a baby, and it doesn't mean that he considers him an equal.
It is said that Dumbledore is the only one Voldemort feared.
OotP Chapter 36: The Only One He Ever Feared
But it is never implied that Voldemort considered Dumbledore his equal. The very thought would probably terrify both of them.
We know that the killing curse doesn't cause any injuries on the body and that it leaves the victim dead.
From the description of the three dead Riddles (Tom's father and grandparents)
plainly, three apparently healthy people did not all drop dead of natural causes on the same night. (GoF)
and later in Moody's class
instantaneously the spider rolled over onto its back, unmarked, but unmistakably dead. (GoF)
and in the next paragraph Moody says
"Not pleasant. And there’s no counter-curse. There’s no blocking it. Only one known person has ever survived it, and he’s sitting right in front of me." (GoF)
So Voldemort has no reason to consider Harry his equal, and even if he did, the Killing Curse is not the right tool to mark anybody, because it leaves no mark. It also doesn't make sense to have someone marked as his equal, when there has been no prior known survivor to the Killing Curse, and Voldemort would definitely not consider himself equal to someone who is dead.
So why does Dumbledore say that Voldemort marked Harry as his equal, and why does Harry accept it when it obviously doesn't make sense? Or, as logic isn't Harry's strong point, why doesn't Hermione notice?
Some remarks to some points of the answers and comments, here for better visibility and formatting.
Thanks to @Bellatrix for providing the quote from Dumbledore that a prophecy is basically meaningless. I will even add where Dumbledore says
"You are setting too much store by the prophecy!" ... "Would it have meant anything? Of course not! Do you think that every prophecy in the Hall of Prophecy has been fulfilled?" (HBP)
But this question was not about the uselessness of the prophecy, but about the actual meaning. We already know that prophecies may or may not be fulfilled and that this in particular isn't, because Voldemort dies by his own curse and not by Harry's hand.
So I'm not convinced by arguments that basically say "it is true because the prophecy said so".
You're interpreting the prophecy way too literally. That's not how prophecy works.
The wording already has a broad range of literal interpretations. If we add more possible interpretations, the prophecy becomes even more useless.
It could not have been necessary for Voldemort to intend to mark Harry as his equal, because Voldemort did not even know that part of the prophecy
The prophecy is either true or it is not, it should not be necessary for people to know (part of) the prophecy for the prophecy to be valid.
by choosing to attack Harry, he is by definition marking him as his equal.
That is a strange definition. By choosing to attack other people, he is by definition marking them as his equal, too?
By going to kill Harry, he was in fact acknowledging that Harry would be his undoing if allowed to live.
No, by going to kill Harry, he was acknowledging that Harry might become a danger to him.
Voldemort only believes in one type of power, which is the standard type of magic. ... He even depends on no one but himself, because ultimately, he does not even see the power in working together. It is probably inconceivable to him that something other than pure magical power could possibly defeat him.
After the fight at the ministry in OotP, Voldemort does run away, either from Dumbledore or from the combined power of the Aurors. The whole year he had hidden himself from the ministry. So he knows he doesn't have to power to take on the whole wizarding world at once. He knows of the advantages of having others work for him. If he thought he could do everything by himself, he wouldn't have the Death Eaters.
Some said that the mark is the fact that he considered Harry a threat and not the scar.
In addition to the quotes I at the top of the question, Dumbledore says
"in marking you with that scar" (OotP)
So it is clear that Dumbledore considers the scar the mark of the prophecy.