Attached is an ert test that demonstrates the problem.  The crux is
that:

  (require 'map)
  (setf (map-elt m key) value)

returns VALUE only in the hash table implementation.  `setf' should
return VALUE in all cases.

For alists it returns either nil or (key . value) depending on whether a
key is inserted or udpated in place.  For plists it returns similarly
variable things.

Here is the output I get from the attached test.  The .el is attached afterwards.

F test-map-setf-alist-insert-key
    (ert-test-failed
     ((should
       (equal
        (setf
         (map-elt alist ...)
         'value)
        'value))
      :form
      (equal
       ((key . value))
       value)
      :value nil :explanation
      (different-types
       ((key . value))
       value)))

F test-map-setf-alist-overwrite-key
    (ert-test-failed
     ((should
       (equal
        (setf
         (map-elt alist ...)
         'value2)
        'value2))
      :form
      (equal nil value2)
      :value nil :explanation
      (different-atoms nil value2)))

F test-map-setf-plist-insert-key
    (ert-test-failed
     ((should
       (equal
        (setf
         (map-elt plist ...)
         'value2)
        'value2))
      :form
      (equal
       (key value key2 value2)
       value2)
      :value nil :explanation
      (different-types
       (key value key2 value2)
       value2)))

F test-map-setf-plist-overwrite-key
    (ert-test-failed
     ((should
       (equal
        (setf
         (map-elt plist ...)
         'value2)
        'value2))
      :form
      (equal
       (key value2)
       value2)
      :value nil :explanation
      (different-types
       (key value2)
       value2)))