There are three basic approaches: sort and remove duplicates (the original bash script); insert all items into a set (e.g. hash table) that only keeps unique copies, and count its size; or probabilistic solutions like Count-Min-Sketch or HyperLogLog. But the problem with the latter is that they are approximate, which doesn't sound ideal when billing customers.

The problem with both of the first two approaches is that they require all items to be stored in memory at the same time. As long as that's true, either the sort or hashtable approach will work fine. But once you run out of RAM on a single machine, it's going to slow way way down as it swaps to and from disk constantly.

To me, the natural solution is to just split the dataset alphabetically into, say, 10 or 100 equal-size jobs, and run these either sequentially or in parallel on 10 or 100 machines. So for example if the unique IDs are random strings of digits, then everything starting with 00 is in the first job, everything starting with 01 is in the second, up to 99. For each job, apply either the sort or the set approach; shouldn't matter much.

(edit) For example, here's sequential pseudocode; the second step is embarrassingly parallel.

    # split the records
    for each record in records_list:
        prefix := record[0:2]
        write record to file "records"+prefix

    # count
    total = 0
    for each records_prefix_file:
        initialize hash_table
        for each record in this records_prefix_file:
            insert record into hash_table, ignoring if already present
        total += size of hash_table