The plaque on the State House building in Hargeisa, capital of Somaliland, is an oblique commemoration to an event that never occurred. It was built in 1952 for a visit to the then British protectorate by the newly crowned Queen Elizabeth II. The Queen never came. These days the half-ruined structure is known for another reason than as the former seat of gin-sipping British colonial officials.

The grounds, including parkland once laid out as a golf course, have bred domed shelters – "bool" they are called – thatched with plastic and segments of scavenged cloth. In places, walls have been tiled with panels of flattened cooking oil cans, which in their repetitions resemble Warhol prints. The bools are low, windowless huts through which the harsh light bleeds messily at the sewn seams to illuminate the kicked up dust. The occupants of this camp sit at the far end of the planet's social spectrum from the State House's first intended guest. Not a monarch and her retinue but refugees from war.

The huts are so densely packed together they block the State House from sight. It is barely visible when approaching the camp, but the monument marks the centre of a labyrinth of winding, narrow lanes where cockerels scrabble. When I reach it at last, I find the State House is not occupied itself save for a single wing of outbuildings. Its rooms are open to the sky, floors scattered with detritus. Glassless window frames swing in the wind.

But it is far from empty. Children clamber over walls of square-cut honey-coloured stone, partly demolished by fighting in the city in 1988. They sit on the floor of what once was a grand reception room to play complex games with piles of pale round pebbles, tossed and snatched from the air by competing hands. Outside, a few young men sit on a veranda painted with graffiti, listening to music. They pull jackets over their heads to hide their faces at our approach and warn against photography.

It is a clue to the identity of many living inside the State House camp: the still anxious victims of the war in the south, in Somalia proper, the country from which Somaliland – recognised by no other state – split in 1991. Victims of the world's worst humanitarian disaster. And conflict, even at a distance from the running gun battles on Mogadishu's streets, imposes its own hierarchies. 

The most recent refugees, the poorest, live at the periphery, farthest from the State House itself. Which is why it is surprising to find Sarida Nour Ahmed, aged 31, a recent arrival, occupying one of the building's few habitable rooms, a few metres square. Once used to house the British governor's staff, these days it is roofed with corrugated metal which leaks in the rain. A bool would be much better, she explains.

Sarida fled from Somalia in March, abandoning three of her 10 children in the chaos of flight. "The situation was unbearable. Mortars were landing during the day. At night there was torture, rape and beatings. At first we thought it was because of the Ethiopian invasion. But things got worse. They came to our houses. Robbed and raped." I ask her who? The Shabaab, she says. The Shabaab. The word means literally "the youth". And it is the story of the victims of the Shabaab's continuing war that I have come to the camps of Somaliland to find.

A sick woman pleads for help at the Burao camp, Somaliland. Photograph: Antonio Olmos

Once comprising the northernmost part of Somalia's failed state, for the past two decades Somaliland has proclaimed itself an independent republic. Stable, if not prosperous, it has become a refuge for Somalis from the south, most making their way up north from Mogadishu. For those from Somalia's southernmost towns it is a dangerous journey that can take several months, with long stretches on foot.

The Shabaab was once one of the Islamist militias attached to the Islamic Courts Union, which, in 2006, brought a semblance of peace to a country that had been wracked by years of internecine violence and warlordism. The Courts were routed after a few months by a western-supported Ethiopian invasion. Now the Ethiopians have gone, too, and a fundamentalist hardcore of the Shabaab is resurgent, Somalia's most bitter tormentor – Africa's own Taliban.

Its masked men, accused by America of being proxies for al-Qaeda, enforce their own notions of justice, seizing suspected collaborators with the feeble new government from their houses and murdering those it regards as opponents, including dozens of local journalists and aid workers. Its feared and secret sharia courts have sentenced women to be buried and stoned to death for adultery or publicly beaten for infringing strict Islamic dress codes. Somalis say that, beyond the facade of harsh and rigid piety, the group robs and kills and sexually assaults with impunity.

Arriving at the State House camp, accompanied by Oxfam, which is helping to support its residents, I ask to talk to the most recent arrivals from Mogadishu and the south. A group of women lead me through a ruined stone doorframe and across a little yard. It is here, in a dark, bare room smelling of smoke from her cooking fire, that I first meet Sarida. In Mogadishu, she tells me, she and her husband had a "proper house" with five rooms. They owned a little shop and sold cold juices and vegetables in the market. These days she washes clothes and skivvies, when she can, to feed her children. She cannot remember the last time they ate meat.

She describes the violence in fragmented snatches that reflect the chaos in a city where all sides – government, African Union peacekeepers, Ethiopians and the Shabaab – fight their pitched battles over civilian neighbourhoods, not caring who is killed.

"First the Shabaab fought with the Ethiopians. When the Ethiopians left," recalls Sarida, "we thought then that Somalis would come together. But it didn't happen." What happened instead, she explains, is that the Shabaab moved to impose its values on Somalis in the large areas it controls, bringing more violence as it did. "Women get 90 lashes even for wearing 'light' clothes," says Sarida. "And for not wearing the veil. But the veil costs money. I didn't have money for a veil..." It is a complaint I hear from many women.

Sarida describes the worst day of her life. She does not cry. Not quite. It was a day that began with mortars falling on her neighbour Amina's house and ended with the loss of three of her children. "To see her in pieces…" she loses her train of thought for a moment. "Mogadishu is a big city. You used to be able to run to another neighbourhood [to escape the fighting], but the fighting was all over the city. I grabbed the children that were close to me and fled with the clothes I was wearing." Her eldest children, aged 12, 11 and 10 – nowhere in sight in the family's panicked impulse to flee – were left behind. So too was Sarida's husband, Abdi Khader. I ask the children's names. She says quietly: "Mohammed, Abdi and Hussein. I cheat myself thinking my husband might have got to the children and rescued them."

But Abdi Khader does not know where Sarida ran to. Or where she is living now. Since that day, she hasn't heard from him. "If I could turn back the clock I would have my husband and my children here with me. But I can't go back."

I had first heard about the brutality of the methods of the Shabaab from Zam Zam Abdi, a courageous 28-year-old Somali women's rights campaigner forced out of Mogadishu by the group. We had met in London almost a year before. Then, Abdi had told me of the note the group posted on her office door: "Stop what you are doing or we will act. Yes or no?" Abdi knew what it meant. It was a phrase gaining notoriety in Mogadishu even then. She had heard the same message delivered on the radio by a pro-Shabaab Imam, received it in emails and in anonymous calls. The same words had been pinned to the body of one of Abdi's friends, murdered by the Shabaab.

It was Abdi's words that had impelled me to Somaliland to search for the group's victims. And it was to Burao that I was heading – Somaliland's second city, and home to the worst of the camps.

The road to Burao takes a sweeping dog leg from Hargeisa down to the coast, before cutting back inland again, crossing an arid plain punctuated by long mesas, hazy in the distance. Visible, too, in places are the remains of Somalia's other wars: wrecked Russian armoured vehicles, rusted and buried to their axles in the sand. Somaliland's camps, however, are a reminder of a more recent conflict: America's war on terror. Far from weakening the Shabaab, the US intervention only appears to have made it stronger.

Beyond the Soviet-built port at Berbera we overtake the Hargeisa bus bound for Mogadishu. It is empty on this leg, but will return full of those fleeing the south. My driver tells me it is good business for those willing to take the risk and drive a truck to Elasha Biyaha, 11 miles from Somalia's capital, at the heart of the Afgoye Corridor, and take on a human cargo desperate to escape.

The Afgoye Corridor. A place synonymous with misery and degradation, hunger and disease. A 20-mile long stretch of road heading west out of Mogadishu, it is home to the world's largest concentration of displaced persons, over half a million living beside the road, many subsisting on boiled leaves. Yet faced with the choice of Mogadishu's gunmen and the horrors of Afgoye, it is Afgoye that many are forced to choose. According to Oxfam, some who end up living there have been displaced three or four times before.

Arriving in Burao I meet one of the luckier ones, Liban Ali Ahmad, 21, who escaped through Elasha Biyaha and the Corridor on a crowded truck a year ago. Lucky, because in his extended family, Liban, a student, could count on two aunts born in Burao who paid for his family to escape and who housed them in the town. Lucky too because he did not have to live in the Corridor, only navigate one of the world's most dangerous roads.

Liban is studying in his green-painted bedroom when I call to visit. He is tall and slim, with sideburns shaved into long slender blades that follow his cheekbones. There are English books stacked in one corner. He cannot afford the fees for he local university where he would like to do a course in business management, so he teaches himself in his room, furnished only with a mattress. 

In Mogadishu, he tells me, his four-times widowed mother was a "khat lady" selling kilo "trees" of the narcotic stems imported from Ethiopia, where it is grown. Her business paid for a rented house in Wada Jir district, close to the airport. "It was bad there because the war was everywhere," Liban remembers. He seems calm as he tells his story, until I notice his hands held in his lap, fingers weaving an invisible cat's cradle of anxiety. After he finished secondary school Liban worked as a private tutor, teaching children at home who could not go to school – Arabic, maths and Somalian.

"I tried for two or three months," he says. "It didn't work out." The families of the children Liban was teaching were fleeing the city, until most of his neighbourhood was empty. "There was supposed to be a ceasefire. But there was fighting and the schools were all closed. So my brother said he wanted to see if the school was open. It wasn't. He climbed into a tree near to our house to play. That's when he was shot."

He calls out into the corridor for 14-year-old Ayanle, a shy and skinny teenager, blind in one white and pupil-less eye. Liban gently helps his brother out of his shirt and then a T-shirt, to show where the bullet went in, piercing Ayanle's chest and bursting through his back. The wounds have healed and puckered to small, dark deformities. "Recently he became sick again," Liban explains: "Because of the bullet." Even after Ayanle's shooting the family tried to stay in their home. "Those six months were terrifying. Even when the children came here they were still terrified. They would ask: 'When are the bullets coming?'"

In Wada Jir they could not go to the marketplace for days. The residents within his neighbourhood were given a 10-minute warning by the Shabaab when the fighting would begin. Told not to move. Not to leave their houses.

"Finally we were trapped in our house for seven days. The smallest children were lying like they were dead. We couldn't give them water. Not fit for humans to drink. In the end I risked my life to go out to get water and something for the kids to eat. We had been discussing it for ages, whether we should escape. That time – those seven days – were the final exam. We decided to leave."

Almost the last to leave their neighbourhood, the family headed for Elasha Biyaha and the Afgoye Corridor with $300, donated by an uncle, to pay for their escape. It was left to Liban to arrange it. He hired a taxi first to take him through the fighting to the Corridor, to hire a truck to take the family out. "It was risky. We left while there was still fighting going on. Some of the vehicles hit mines and exploded. You either leave safely or end like this," he adds bleakly.

The camps in Burao are ugly places. There are no schools or health facilities. Not even proper sanitation. Privately owned, the residents are charged to occupy their huts and draw water from the solitary well. The 15 May camp is the worst: its huts border a field covered with rubbish, where camels are herded beneath the trees. On one visit I hear the sound of drumming, and enter a hut to find it crowded with men and women at a Sufi ceremony to drive spirits from a woman kneeling on the floor, pungent incense wafting through the hut.

In her bool nearby, Quresh Ise Nour has a baby wrapped in a pink blanket in her arms, born a week before on the road to Burao, hair slicked wet with sweat. Tradition demands that Quresh stays indoors, confined, for 40 days. Without a husband to support her, she must rely on other women from the camp, who go to Burao to beg, to bring her food. When the pickings are slim, or non-existent, Quresh cannot eat, cannot produce enough breast milk and her baby goes hungry. Her hut is a new one; the older ones, with their multiple layers of fabric, are better, she explains, because they are cooler.

Quresh is the camp's most recent arrival. Her husband was killed in the fighting in Mogadishu. "He was a casual worker. He left in the morning to go to work with his wheelbarrow. He was away for only four hours," she says, not quite believing what could happen in so short a period of time. "Some friends he used to work with brought his body back in his own barrow. His name was Mohammad Hassan Ali." Fleeing Mogadishu, she ran with her children to Afgoye.

"You would always hear the bullets. Then everyone would try to run. When you would get back to your home the mortar shells would land on the huts. It is because the Shabaab would use the bools for their defences. The government forces would come in vehicles and uniforms. The Shabaab would be in civilian clothes with rifles and RPGs. They controlled the area we were in. They would mine all the routes that they believed the government troops might enter by. You can't tell anyone," she explains, seriously. "They ask all the time: 'Where are you going?' Their faces are covered with scarves so you only see their eyes. Most of the time I stayed indoors." Because of the mines, the African Union troops would not come into the camp. "They would come close and mortar where we lived, so the Shabaab would say: 'These are bad people'. But with the Shabaab you never got kind words."

I start to understand how the Shabaab work. Others tell me of masked young men with megaphones walking by the houses, shouting out the rules. I hear stories of men taken from their homes and later found shot. All blamed on the Shabaab. A woman called Busharo tells me how the men arrived in her hut at night asking for her husband. Not finding him, they burned down her home.

Quresh says: "If you don't have a hijab, the Shabaab come to you. They came to me. I told them my husband was dead and I had no money. They ran into my house. I thought there must have been fighting. They said: "Woman, why are you not wearing a veil?" There were two of them with a whip made from woven tyre rubber. They hit me on the back and buttocks. Even now you can see the marks. A month later I left."

The stories of the Shabaab's cruelties accumulate as I tour the camps. One man tells me how they stopped him returning from his work and stole the fruit he had bought intended for his children, warning him not to resist. They said his life was worth more than some fruit. I hear the story of how the Shabaab tried to drag a neighbour's wife out of his house to rape her. How he was shot when he tried to stop them. Patterns emerge. Visits by day and night by armed men seeking friends and family, often accompanied by a press-ganged neighbour or passer-by, snatched from the street, and ordered to indicate the house they seek. 

Even as they tell their tales, the fear of the Shabaab still clings to these people. I ask for names, descriptions of the perpetrators, even nicknames they might have given individual Shabaab fighters. But no one is comfortable to say "it was this person". The reason, I am told at last, is that there are Shabaab sympathisers in the camps, perhaps even among those who gather to listen to the interviews in curious groups.

There is one man, in particular, who I am looking for, Abdi Abdullahi Jimale, a 38-year-old mechanic from Mogadishu and sometime farmer who came to Burao nine months before. I already know the bare bones of his awful story: how he lost four of his children to hunger and violence. These days he makes a living through odd jobs and a few days' work at the local tannery when he can. Otherwise he sends his girls into Burao to beg. Abdi calls the Shabaab "al-Qaeda". "The Shabaab are everywhere among the people. They take what you have and leave you empty except for sorrow. When they started appearing they would say, 'You can't watch videos at home. You can't listen to music.' When the fighting came I lost two of my children. I didn't even have a chance to bury their bodies." He tells me that their names were Osman, aged four, and Mohammed, five. "I was sitting in my house when I heard the bullets. A little later a shell fell on my house. I carried some of the children and my wife the others, then we ran away." Their ordeal was not yet over. "I had two other children who died on the way to Baladweyne. They were small children.

We walked a long way and they were very tired. They were one and three, and we were walking for eight days. We had put the children on a donkey cart at first, but some people took the donkey cart and the things we had in it." The rest of the family was saved through the intervention of a group of nomadic pastoralists who killed a goat for them to eat

I am in my hotel in Burao when a text message comes in. There has been a fire at the State House camp. The details change. Six huts destroyed, the message says at first, then later 12. A child has been killed. We head straight to Hargeisa and the State House. It is a girl of five who has been killed. The fire jumped from bool to bool in a matter of seconds, the flames enveloping the dry panels of fabric, collapsing it upon her. There is a clearing, now, among the huts

Someone has handed those who have lost their homes brightly coloured plastic buckets, to collect what is left of their possessions. The women hunt among the ashes for pots and pans, but there is almost nothing left but an accumulation of flaking ash. The shelters have been reduced in places to nothing more than a stubby spine of charcoal nubs, all that is left of poles that once supported them. A few torn pages from school books are blowing among the ashes.