Does this picture help you to understand how associative caches work structurally?
borrowed from here
In a nutshell the block offset bits determine your block size (how many bytes are in a cache row, how many columns if you will). The index bits determine how many rows are in each set. The capacity of the cache is therefor 2^(blockoffsetbits + indexbits) * #sets. In this case that is 2^(4+4) * 4 = 256*4 = 1 kilobyte.
For the same size cache (capacity), if you were to go from 4-way to two-way set associative, it two way associative, you could do so by either doubling the rows in each set or by doubling the columns in each set, which is to say doubling the number of cache lines or doubling the block size.
If you were to choose to double the number of rows, you would end up with your 12-bit address being broken into a 5-bit index and a 4-bit block offset, leaving a 3-bit tag.
If you were to choose to double the block size, you would end up with your 12-bit address being broken into a 4-bit index, a 5-bit block offset, leaving a 3-bit tag.
So to re-iterate, I think the governing formulas for associative caches are:
Cache Capacity = (Block Size in Bytes) * (Blocks per Set) * (Number of Sets)
Index Bits = LOG2(Blocks per Set)
Block Offset Bits = LOG2(Block Size in Bytes)
Tag Bits = (Address Bits) - (Index Bits) - (Block Offset Bits)
In your originally stated example, I don't think you can deduce the size of the cache based on the size of your respective address bit fields without making an assumption about the associativity. If it is 2-way associative, then you could say:
Cache Capacity = (2^6) * (2^10) * (2) = 2^18 = 2^8 kilobytes = 256 kilobytes. I'm not sure how you came up with 128 kilobytes. That would be the case if it were 1-way associative (direct mapped).
For a 128kB (2^17 bytes) cache capacity, you could make a 4-way associative cache with a 64 byte block size by saying:
2^17 = 2^6 * (Blocks per Set) * 4
Blocks per Set = 2^17 / 2^6 / 2^2 = 2^9 = 512
... and therefore allocating 9 index bits, 4 block offset bits, and the rest (19) tag bits.