Measuring similarity of music, using lossy compression
Is there a good way to use them to measure how similar the two clips
  are?


This is a very sane intuition but something I have rarely seen in the literature - outside the peripheral idea of doing feature extraction from compressed streams (and the motivation here is just the reduced computational burden).

I think the major reason is that audio codecs do not store a perceptual representation of the audio data. Instead, they store a very coding-centric representation of audio - entropy-coded, quantized, coefficients of a transform - chosen so that the distortion between the original and the encoded signal falls below the threshold of perception. In a sense, looking at a compressed audio stream does not tell you anything about how a human would perceive the audio signal. It just tells you that anything that would fall below the perception thresholds has been taken away. The codec "carves" around the meaningful audio signal, but never touches it.


  where L(x) is the length of the compression of sound clip x, and C1||C2 is the result of concatenating the two clips?


This makes sense on strings - I think this idea is found in some papers by Cilibrasi or Vitanyi - but this is not how audio codecs work. The audio codecs you mention are designed to process streaming audio with low latency, so they only "see" a short window of the signal at a time and do not attempt to eliminate long term redundancy. Just like JPEG for images. Copying 10 instances of the same note one after the other will result in a file 10x as large. Audio codecs have a fixed bit-rate, or an adaptive bit-rate that is adapted according to the content of the narrow window of signal that the codec sees.

The redundancy eliminated by an audio codec is very short-term.

Your idea would require a much more sophisticated "objet oriented" codec that attempts to decompose the audio into a hierarchy of objects, such as notes. This idea is still in its infancy in the academic world.

Another way to look at it is to check if the decoding process bears similarity with a generative model of the signal. This is the case for some string compression algorithms, where the compression process recovers something akin to a generative grammar of the string (Sequitur, factor oracles...). This is the case for LPC-based speech codecs in which the LP coefficients embed knowledge about the articulation, and the residual knowledge about prosody and voicing/unvoicing - the compressed stream can be seen as data for a speech synthesizer. But this is not the case for general purpose audio codecs like the ones you mention - the decoder bears no similarities with the music production process.


  Or maybe find the highest bitrate such that F(C1) is close to F(C2)) via a simple metric (e.g., L2 norm applied to the FFT spectrum)


You might do the opposite - look at the bitrate under which the clips become indistinguishable, but ultimately it wouldn't be that much easier than comparing sinusoidal representations pruned by a perceptual function.