Here is how I would approach it:

use warnings;
use strict;

my %barcode_hash = (
    1 => ['AGCTCGTTGTTCGATCCA','GAGAGATAGATGATAGTG','TTTT_CCCC',0],
    2 => ['AGCTCGTTGTTCGATCCA','GAGAGATAGATGATAGTG','TTTT_AAAA',0],
    3 => ['AGCTCGTTGTTCGATCCA','GAGAGATAGATGATAGTG','TTTT_BBBB',0],
    4 => ['AGCTCGTTGTTCGATCCA','GAGAGATAGATGATAGTG','TTTT_AAAA',0],
);

Find_and_Increment ('TTTT_AAAA');
Find_and_Increment ('TTTT_CCCC');
Find_and_Increment ('TTTT_AAAA');

#--------------------
sub Find_and_Increment{
    my ($pair) = @_;

    for my $k (keys %barcode_hash){
       next unless ( my $aref = $barcode_hash{$k} ) -> [2] eq $pair;
       $aref->[3]++;
       print "$pair found at $k, $aref->[3] time(s)\n";
    }
}
[download]

$ perl search_hash.pl 
TTTT_AAAA found at 4, 1 time(s)
TTTT_AAAA found at 2, 1 time(s)
TTTT_CCCC found at 1, 1 time(s)
TTTT_AAAA found at 4, 2 time(s)
TTTT_AAAA found at 2, 2 time(s)
[download]

I was wondering why you sort the keys in each example ?

Hashes are unordered, and keys will return the keys in a random order. Try removing the sort from my code, and you'll see that in the second code example, the arrays in the %lookup "hash of arrays" data structure will be in a random order across multiple runs of the program, and the output of both code examples will be in a random order across multiple runs. This may or may not be important in your case, I just did the sort keys so that the output would always be in the same order. This can also make testing easier, since tests wouldn't have to account for the randomness. If your hashes are large then the sort may slow down your program a bit. Personally I would suggest doing sort keys for the consistency, unless you know for a fact that the order doesn't matter in your case (e.g. if all you are doing is counting), or the speed impact becomes a problem.