Three of the four suspects were arrested on Thursday over the brutal killing of the two hikers, as investigators probed a link to Islamic extremism.
"The video showing the arrested individuals... pledging allegiance to Daesh was recorded last week before the execution of the criminal acts we are investigating," the Rabat prosecutor said in a statement using the using alternative name for Isis and confirming the authenticity of the video.
Government spokesman Mustapha Khalfi described the killings as a "criminal and terrorist act", while Prime Minister Saad Eddine El Othmani called them a "stab in the back of Morocco and Moroccans".
That was in reference to the likely negative impact the murders will have on the North African country's vital tourism sector -- which accounts for 10 percent of national income.
The arrests in the city of Marrakesh follow a first arrest on Monday of a man suspected of belonging to an Islamic extremist group, hours after the discovery of the two women's bodies in the High Atlas mountains of southern Morocco.
"The suspects have been arrested" and investigators were in the process of "verifying the terrorist motive, which is supported by the evidence and the findings of inquiries," said the central judicial investigations office.
The bodies of Danish student Louisa Vesterager Jespersen, 24, and 28-year-old Maren Ueland from Norway were found on Monday, after the two friends had pitched their tent at an isolated mountain site two hours' walk from the tourist village of Imlil.
Police have focused on the terrorism line of inquiry since arresting the first suspect in a poor neighbourhood of the region's main city of Marrakesh, which is a magnet for foreign tourists.
"The radical Islamist line has not been removed, because of the profile of the (first) suspect arrested and the three" others, who have links to radical Islamic circles, a source close to the investigation told AFP on Wednesday.
Investigators released pictures of three of those arrested, who were identified as Rachid Afatti, Ouaziad Younes and Ejjoud Abdessamad.
In one of the black and white photos circulated by the authorities, a suspect wears white robes and a white skullcap, and has a long beard.
Photo: AFP / MOROCCAN POLICE /Ritzau Scanpix
The second suspect also has a long beard, while the third has a thin face and a goatee.
But in another picture released by police after they were detained, the three are freshly shaven and wearing plain clothes.
Rachid Afatti (L), Ouziad Younes (C), and Ejjoud Abdessamad (R), the three suspects arrested on Thursday. Photo: AFP / MOROCCAN POLICE /Ritzau Scanpix
All three hail from Marrakesh, and one of them had "a court record linked to terrorist acts", police spokesman Boubker Sabik said.
Danish Prime Minister Lars Løkke Rasmussen denounced what he called a "beastly crime".
Addressing reporters, Rasmussen said "like the whole world, we react with consternation, disgust and a profound sadness."
Norway's Prime Minister Erna Solberg condemned what she called a "brutal and meaningless attack on innocents".
In Rabat, the government spokesman highlighted the efforts of the security services in the fight against terrorism by hailing the arrest in "record time" of the alleged suspects in the double murder.
Moroccan authorities were still working to determine the authenticity of a video posted on social media networks allegedly showing the murder of one of the tourists, a prosecutor said in a statement.
The killings have sparked fears of a hit to Morocco's crucial tourist sector as the kingdom's relative security has always been a major selling point.
"What most of us had feared -- that is to say a terrorist angle to the double crime in the region of Imlil, has been confirmed," said leading news website Medias 24.
"Shock, sadness and revulsion are perceptible in Morocco," it added.
Traumatised by the murders, residents of Imlil are deeply fearful for their livelihoods, and have helped investigators in identifying suspects, a tourism sector source told AFP.
Morocco has been spared jihadist attacks since 2011, when a bomb attack on a cafe in Marrakesh's famed Jamaa El Fna Square killed 17 people, most of them European tourists.
An attack in the North African state's financial capital Casablanca killed 33 people in 2003.