Right. However, AVX and SSE registers aren't just big 512-128 bit numbers. But rather arrays of bytes/shorts/ints/floats/doubles.
Actually, you can add one 512-bit register with another 512 bit register in a single instruction. You won't get a carry from a segment to a segment but nialo's general idea can be implemented.
How fast it can be done is another topic.
If instead of 16 512bit registers, we simply want to increment the appropriate section of one big register, we can add 2^(byte * n), where byte is the value of the byte in question, and n is the number of bits we're using to count the results.