Since every thread in a block all update the same block local variable, we still need locks to atomically update the block-specific list of lists, right?

Yes I think we still need locks. However, maybe we could split each grid again to different blocks (areas) when merging, hence we only need to lock a specific block when updating? Maybe this can reduce the number of locks we need