I'm experienced with BBQ and cooking meats, but I've never done a leg of lamb on the BBQ before.
For marinade, I like lemon zest, garlic, and thyme. Be sure to let the meat come to room temp before cooking. Are you cooking with bone in or not? I've had good luck cooking lamb on the bone, but it's often taken longer than I expected, probably due to very low heat. But the meat was delicious.
Aussies love lamb and cook it anywhere. Even on a BBQ! One of my favourites is made with a mix of plain Greek yoghurt, honey, cumin, salt and pepper. Mix it up, spread it on and cook low and slow. Or a dry rub of salt, pepper and crushed rosemary leaves, is simple and hard to beat.
My favorite lamb lately involves a marinade of soy, sherry, garlic and oil, then a dry sprinkle of toasted cumin seed, szechuan peppercorns and salt. I've done a whole lamb leg, or have cut it into strips and both yield flavorful, tender lamb. We cook over indirect heat for a couple hours, then sear it over direct heat at the end. And you might want to use a drip pan.