Trees don't really hold hills together too well, although surface plants like crown vetch or grass do. Think how many times you've seen a hill slide away, toppling trees with them: Our woods are full of 'em.
Trees will sometimes degrade hillsides the same way they can degrade dams. First, the roots can grow through on the water side and facilitate migration of water along the root/clay boundary into the dam through simple hydraulic pressure. If those roots also grow out to the outside of the dam, the water's got a potential straight path to a new level. Second and potentially worse, when a tree or just a root dies, it decomposes and can eventually leave a tunnel for water to go through. And if the dam ever needs work, there is no way to be sure that all the roots have been removed to ensure a good seal afterwards. We had a very experienced pond builder out a couple of years ago with a request to rework a dam with a lot of middle-aged trees on it, and he simply refused (which turned out to be good salesmanship on his part; we love our new pond /w3tcompact/icons/laugh.gif).
Whether or not cut down all your trees is another question, unless theree signs of trouble: Just be aware of the risks. Some trees shoot their roots straight out to water as quick as they can; others are much more polite about it. Our old dam was probably 80-90 years old and still holding water, although at least in part this was because it was silted in so much that the water was only about 2' deep at the dam edge. If you do take out the trees, I wouldn't worry too much about removing the root balls unless there are some that clearly have grown into the pond, and those can be cut out and sealed with either clay or Bentonite.
