We just had this problem on the weekend. Ruby had sap on her feet and between her toes. We just took her to the beach to run and play in the water. The gravel (no sandy beach here) and the salt water just washed her feet and no more sap. Worked great! Other than that I think you would have to use solvent of some type, which I wouldn't want to use on my dog. You could also try dish soap, although I don't know if that would work.