The Quran mentions crucifixion even before Moses ( عليه السلام), at the time of Joseph ( عليه السلام) . The interpretation of the dream of one of his companions in prison was that he would be crucified:
يا صاحبي السجن أما أحدكما فيسقي ربه خمرا وأما الآخر فيصلب فتأكل الطير من رأسه قضي الأمر الذي فيه تستفتيان
O two companions of prison, as for one of you, he will give drink to his master of wine; but as for the other, he will be crucified, and the birds will eat from his head. The matter has been decreed about which you both inquire."
— Quran 12:41
Note that تصليب (translated as crucify) is simply the act of suspending and displaying the body of the deceased. There is testimony to it in the Torah:
Then the Lord said to Moses, “Take all the leaders of the people and hang the offenders before the Lord, out in the sun, that the fierce anger of the Lord may turn away from Israel.
— Numbers 25:4
You may see various commentators have called this crucifixion:
refers to the punishment of crucifixion, a mode of capital punishment which was adopted by most of the nations of antiquity
Either by way of impalement or by way of crucifixion, both of which were familiar modes of punishment.
When someone is convicted of a crime punishable by death and is executed, and you hang him on a tree
— Deuteronomy 21:22
Within three days Pharaoh will lift off your head and impale your body on a pole. And the birds will eat away your flesh.
— Genesis 40:19
Regarding your claim that there is no other evidence for 'crucifixion' before the 6th century BCE, then maybe that applies to specific variants of the punishment: such as where a cross is used or where the hands and feet are nailed to the wood, or where the person is killed after being hanged. All of these are not essential.
The following article is also relevant: https://www.islamic-awareness.org/quran/contrad/external/crucify.html