Use up all characters to form words
Since "the chars set length could be up to hundreds", it can easily contain enough letters to form any word in an English dictionary. In such a case prune_words would not prune any words. This makes me think the pruning is an example of premature optimization.
Instead of using Counter to check a match, I believe it would be faster to compare sorted lists of characters, i.e. compare sorted("".join(comb)) to a pre-computed sorted(char_set).
Copying a Counter by Counter(char_count) is faster than by copy.deepcopy.
To check if all counts are zeros you don't need the list comprehension as you can simply use if not any(temp_count.itervalues())
You check lots of combinations that are the wrong length. Even though the length check is the first thing inside the loop, it would be better to generate the combinations in a way that allows you to back off when the combined length exceeds the length of char_set. I would use recursion to explore the combinations.
A more clever approach might be found from representing the dictionary as a prefix tree.