I've had a lot of luck with getting iguanas to paper train, I would imagine it would be pretty much the same with a tegu. I generally start with the basking spot right over the paper, so they spend time on it. Once they start going there, generally they want to return to that spot to go. Now I have my iguana's basking spot out in another room near some big windows, but he comes across the whole house to the back office to use the paper when he has to go. I had an iguana years ago that would use the cat's litter box, but that was completely accidental "training'.
