First of all, you can simplify the map to return 0when there is no key:
val map0 = Map.empty[Int, Int] withDefaultValue 0
map(key) map.getOrElse(key, 0).
-, Tuple2. key -> value Tuple2(key, value).
-, if ... then ... else. :
def addKey(map: Map[Int, Int], key: Int) = map + (key -> (map(key) + 1))
val map1 = addKey(map0, key1)
val map2 = addKey(map1, key2)
tailRecFunction(someArg, map2)