I think the culprit is here. (counted? (keys {:a 1})) returns false, so this is actually a lie :)
I think you cannot provide a default implementation and should instead force the users to define count themselves.
Right now defining count myself within def-map-type solves the performance issue.