Is there a way to sign a message so that any subset can be verified? I would like to know if there's a scheme that can allow something like the following:

Alice signs a message $M$ with signature $S$ and gives it to Bob and Mallory.
Bob can present any subset of $M$, along with $S$, to Victor, who can verify that the subset matches $M$.
If Mallory changes some bits of $M$, then sends a subset of the bits to Victor, Victor can know that the message has been tampered with. (Of course, Mallory should not be able to construct a valid signature that would allow her tampered-with bits to be verified).

For example, say

Alice's message $M$ is $100100$, and the signature is $101$.
Bob will send Victor $M[0]=1, M[4]=0, signature=101$, and Victor will verify that those bits match $M$.
Mallory will send Victor $M[0]=1, M[4]=1, signature=101$ (this is malicious, since $M[4]$ does not equal $1$ in $M$). Victor will notice this and refuse to verify.

Does a scheme like this exist?
I think that there are somewhat naive solutions (for example, perhaps the signature could consist of several sub-signatures: each bit and its index in $M$ are signed, and the results are concatenated), but I am hoping for something where the signature is short relative to the size of the message.
We can easily see that the signature must be at least as large as the message.  Otherwise, it would be impossible to verify any arbitrary single bit.  Signing  a message with n bits must necessarily must involve a signature that can validate n unrelated 1 bit message subsets.
However, if we assume Bob and Mallory are given copies of the message, there may be opportunities where computations are done over the entire message, but not transmitting the entire message.  This could help reduce the signature size.
You may be interested in Merkle Trees.  I don't know if they are exactly what you are looking for, but they provide some interesting approaches for proving things about contiguous subsets of messages.   In a worst case scenario, you would have to send Victor effectively the entire Merkle tree.  However, for revealing small fractions of the tree, you may be able to keep a large portion of the information out of the message.  You only have to reveal the sibling leaves for every bit you send, which would not reveal the whole message, while still authenticating it as a subset.
There are a few cryptocurrency algorithms out there which leverage this for micropayments.  Alice generates a list of coins, puts them in a Merkle tree, and then gets the top of the tree signed by Victor.  She then gives this signed top to Bob, who authenticates it with Victor (online or offline).  After this point, Alice can send Bob a coin simply by revealing it, and all of the sibling internal nodes required to prove it was part of her list of coins.  These algorithms, of course, strive to be efficient.  They expose the coins in order, so they only ever have to reveal contiguous subsets, not the arbitrary ones you might need.  This keeps the message traffic down to O(n log m) for n coins transferred out of m coins minted.
Another approach would be to carefully select the message that Alice constructs to have the properties you desire, rather than being an arbitrary message.  Zero Knowledge Proofs are full of clever situations where Bob has to demonstrate information about a message while carefully controlling how much information is transmitted.
One thing you should definitely watch out for is whether there is any issue with Eve computing the message from just S and the message traffic between Bob and Victor.  The content of the message could start getting leaked.  If you know the internal node over a group of n bytes, you can brute force those n bytes, recovering a part of the message that hadn't been revealed by Bob.  But if the goal is simply to provide subsets of a verified message to Victor, that may be acceptable.