How should I incrementally sign a large set of documents?
a new signature incrementally (in the sense of Bellare, et al.) which may be verified incrementally


IMHO this seems to be related to long content, where for a (relatively) small update, the "re-reading" the whole content may be not practical. If you have a large set of smaller documents (4kB) I see no reason why you should treat them as one large content.

I don't know if it will help you, but this is what I've see in one big publishing organization, where they need to ensure integrity of the published (legal) content. 


a hash is computed for each content
there a list of published documents and a composite hash of the hashes of each document (sorted list)
the composite hash is signed 


using a HSM it requires user intervention (manual PIN entry) to sign anything, so they sign only the whole list ensuring integrity on level of the whole list of documents. In this case the list is more or less static (it doesn't change)


  Sign H' with the private key.


effectively that's what the publishing organization is doing - just skipping steps 2 and 3. If a new content is added / removed / updated, just content of the small document is to be hashed and the list of document hashes is updated (and signed) yes, you will need to maintain a sorted list of the documents