efficient different sized list comparisons
Nothing is going to be superfast, and there's a lot of data there (half a million results, to start with), but the following should fit in your time and space budget on modern hardware.
If possible, start by sorting the lists by length, from longest to shortest. (I don't mean sort each lists; the order of elements in the list is irrelevant. I mean, sort the collection of lists so that you can process the longest list first.) The only point of doing this is to allow the similarity metrics to be stored in a half-diagonal matrix instead of full matrix, which saves half the matrix space. So if you don't know the length of the lists before you start, it's not a crisis; it just means that you'll need a bit more space.
Note 1: The important thing is that the metric you propose is completely symmetric as long as no list has repeated elements.Without repeated elements, the metric is simply |A⋂B|, regardless of whether A or B is longer, so when you compute the size of the intersection of A and B you could fill in the similarity matrix for both (A,B) and (B,A).)
Note 2: The description of the algorithm seemed confusing to me when I reread it so I changed the word "list" to "list" when it refers to one of the thousand input lists, leaving "list" to mean an ordinary Python list. Because lists can't be keys in Python dictionaries, working on the assumption that lists are implemented as lists, it's necessary to somehow identify each list with an identifier which can be used as a key. I hope that's clear.
The Algorithm:
We need two auxiliary structures: one is the (half-diagonal) result matrix, keyed by pairs of list identifiers, which we initialize to all 0s. The other one is a dictionary keyed by unique data element, mapping onto a list of list identifiers.
Then, taking each list in turn, for each element in that list we do the following:

If the element is not yet present in the dictionary, add it, mapping to a single element list consisting of the current list's identifier.
If the element is present in the dictionary but the last element in the corresponding list of ids is the current id, then we've found a repeated element. Since we don't expect repeated elements, either ignore it or issue an error message.
Otherwise, we've seen the element before and we have a list of identifiers of lists in which the element appears. For each such identifier, increment the similarity count between the current identifier and the identifier in the list. (Note that if we scan lists in reverse order by length, all the identifiers in the list correspond to lists which are at least as long as the current list, which is why we sorted the lists in the first place.) Finally, append the current identifier to the end of the list, so that the next time that data element is found, the current list will be present.

That's it. The space requirement is O(N2 + M) where N is the number of lists and M is the total size of all the lists. The time requirement is essentially O(M2) in the worst case -- that being the case where every list has exactly one element and they are all the same element. (More precisely, it's the sum of the squares of the frequencies of each unique element.)
I wish to compare around 1000 lists of varying size. Each list might have thousands of items. I want to compare each pair of lists, so potentially around 500000 comparisons. Each comparison consists of counting how many of the smaller list exists in the larger list (if same size, pick either list).Ultimately I want to cluster the lists using these counts. I want to be able to do this for two types of data: 

any textual data
strings of binary digits of the same length.

Is there an efficient way of doing this in python? I've looked at LShash and other clustering related algorithms, but they seem to require same length lists. TIA.
An example to try to clarify what I am aiming to do:
List A: car, dig, dog, the.
List B: fish, the, dog.
(No repeats in any list. Not sorted although I suppose they could be fairly easily. Size of lists varies.)
Result:2, since 'dog' and 'the' are in both lists. 
In reality the length of each list can be thousands and there are around 1000 such lists, each having to be compared with every other.
Continuing the example:
List C: dog, the, a, fish, fry.
Results:
AB: 2
AC: 2
BC: 3