(This is a structure already in use that I'm speccing for documentation purposes. I wouldn't generally design something that functions both as a record and as a map of arbitrary well-typed values.)

Does s/merge a s/map-of and s/keys help?

That was my first thought, but I'm not seeing a way to write the map-of part. If I did (map-of string? string?), the special keys and values would fail validation.

yes, you can do this by spec'ing it as a collection of kv pairs and then describe the pairs. I have a blog post about the destructuring spec at https://cognitect.com/blog/2017/1/3/spec-destructuring that has this characteristic

the key is you want (s/every (s/or ...kv-tuple-shapes...) :into {})

Hmm, I've been defaulting to using coll-of rather than every, but I'm seeing that it blows up when I try to do that with :into {}

blows up how?

(s/conform (s/coll-of (s/cat :k string? :v string?) :into {}) {"foo" "bar" "baz" "bork"})

Execution error (Error) at (<cljs repl>:1).
nth not supported on this type cljs.core/PersistentArrayMap
=> :repl/exception!

no, that's why the example above uses s/every instead

Okay, figured that might be the case, it's just surprising to me

coll-of assumes the coll is nth-able (which maps aren't). we may actually have a ticket to consider that, don't remember