Collection has a method for adding elements. For Map, the only thing that could be added is instances of Map.Entry. But adding any Map.Entry is dangerous, as it requires extra checks to make sure there is no other Map.Entry with the same key. Also, the implementing class of Map.Entry matters.
So instead of having Map extend Collection, Map provides three views to its data that are collections: keySet() returns a Set view of the keys only, values() returns a Collection view of the values only, and entrySet() returns a Set view of the Map.Entry instances. All three allow for removal of elements, but adding can only be done using Map's own put and putAll methods. Calling add or addAll on one of the views will throw a RuntimeException (UnsupportedOperationException if I recall correctly).
You could see a Map as a collection of key-value pairs. The designers of the Java collections library could have chosen to implement a Map like that, but they didn't. I know other programming languages in which the Map is indeed a Collection of key-value pairs. So, ultimately there's no logical reason why a Map could not possibly be a Collection, it comes down to a design choice that probably Joshua Bloch made years ago. Rob already explained some of the reasons why it might have been designed like this.