In general: play offensively, don't wait for the enemy come to you. Bring an army of guards with you for protection, at the early stages of the game this will be preachers and warriors, you'll want mostly preachers (10+).

Experiment with different spells, and/or watch the effects of spells cast on you to learn what is effective.
- Lightning is great for killing the enemy shaman, find out where she is sitting (often in a tower) and cast it on her.
- Convert spell is very good at the start of each level to give you 'free' braves. Immediately build a lot of huts, plus a Training building for Warriors and Preachers.
- Swamp can be useful for defending narrow approaches, just make sure your own people don't walk on it too!

I believe there is a totem somewhere on this level which will create a land bridge between the two tribes, this will move some of the enemy's attention away from you. You can't get to this totem, but you can learn Hypnotise, then cast it on the enemy who's standing near the totem

I think your main problem is that you just aren't expanding quickly enough or far enough.

1) Grab the Convert spell from the first Vault of Knowledge right at the start and Convert as many wildmen as you can.
2) Build as many huts as you can. If you hold down Ctrl when clicking you can spam huts quite easily.
3) Look at the population tab, select your idle braves and put them on building projects.

These are very important. Don't stop doing any of them until you hit your population cap (199). Do them on every level.

There is also a trick to this level, that you can hypnotise the guy on the island with the totem to raise a land bridge between the two tribes. However, the important thing is to build up your settlement as fast as you can. You can win without that trick, but you won't win if you aren't building up your settlement, and as the levels get harder you will have to learn to do this.

Also, use your swamps on the Matak (green) shaman when she attacks. This will kill her, wipe out the warriors she attacks with, and will kill her again when she next attacks using the same path. Another thing you can do with the swamp is place it on the guard tower that the Chumara shaman likes to hang out in. She will keep going back to it and will die ten times before the swamp disappears.