To get back on topic
Try fenceing off part of the garden, and put him in there at the times you would normally take him for a walk. After a day or two he'll get the idea.
The other big advantage is that all the doings are in one place saving you having to search the whole garden (and you always miss some) when you clean up, not a pleasant job if you have to miss a day or two.