nitrates...

Nitrates in tap water vary according to countries and water companys. In the UK, levels of 50ppm are the upper acceptable limits; in the US this is lower.

The general rule of thumb for aquariums is that 40ppm is the upper level, with 20ppm desirable. I use Seachem's Purigen pouches to reduce my nitrates from 50ppm to 20ppm (I have 2, 1 in each filter).

Nitrates of 0ppm are achievable, but typically in planted tanks which doesn't really apply to Lake Malawi tanks, with rocks the preferred decoration.

You have to keep in mind that your nitrates are going to decrease at the same rate of your water changes. So, a 60% water change will only decrease your nitrates by 60%, assuming your tap water does not have high levels of ammonia, nitrite, or nitrate.

I think 10ppm is high for tap water in the US, but you can check with your local water authority and google governmental regulations for what is considered safe.

You'll never get zero. Try for 30ppm.

If your water change only brought it down to 40ppm, I'd do another 60% change in a couple days to bring it under 20ppm. From then on you might be able to get by with a weekly 50% change or you might have to do a weekly 50% and midweek 25%. I thought bigger tanks were less trouble. Guess I was wrong. Doesn't sound like alot fish for a 125g. either. The 10ppm in your tap water is the biggest culpret I guess. Like DRansome said you might have to try for 30ppm and be happy with that. My fish don't really show signs of stress even at 40ppm but I don't like it lol.