remove() (in Map as well as in Collection) is not generic because you should be able to pass in any type of object to remove(). The object removed does not have to be the same type as the object that you pass in to remove(); it only requires that they be equal. From the specification of remove(), remove(o) removes the object e such that (o==null ? e==null : o.equals(e)) is true. Note that there is nothing requiring o and e to be the same type. This follows from the fact that the equals() method takes in an Object as parameter, not just the same type as the object.
Although, it may be commonly true that many classes have equals() defined so that its objects can only be equal to objects of its own class, that is certainly not always the case. For example, the specification for List.equals() says that two List objects are equal if they are both Lists and have the same contents, even if they are different implementations of List. So coming back to the example in this question, it is possible to have a Map<ArrayList, Something> and for me to call remove() with a LinkedList as argument, and it should remove the key which is a list with the same contents. This would not be possible if remove() were generic and restricted its argument type.