Are you using the latest version of samtools and HTSlib? If not, please specify.

$ samtools --version
samtools 1.11
Using htslib 1.11
Copyright (C) 2020 Genome Research Ltd.

Please describe your environment.

• OS: Linux 4.15.0-135-generic
• machine architecture: x86_64
• compiler: gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0

Please specify the steps taken to generate the issue, the command you are running and the relevant output.

Used timeout, time and grep to show how rapidly a single record should be found (... used to shorten fields for report purposes):

$ timeout 5s bash -c 'time(samtools view -f 512  input.bam | grep -m 1 -n mm:A:Y)'
1:HX5_27130:3:1121:1996:54805	595	chr1	9996	46	76S75M	=	10040	-31	CG...AC	-...A	AS:i:60	XS:i:55	XA:Z:chr7...,3;	MQ:i:40	MC:Z:67M84S	ms:i:2761	NM:i:8	MD:Z:0N0N0N0N0N14A5A5A43	mm:A:Y	RG:Z:390722

real	0m0.010s
user	0m0.011s
sys	0m0.000s

This filtering should be possible by samtools view -f 512 -d mm:Y from what the docs indicate:

-d STR:STR
only include reads with tag STR and associated value STR [null]

$ timeout 5s bash -c 'time(samtools view -f 512 -d mm:Y /nfs/irods-cgp-sr14-sdf/CANT/intproj/7086/sample/PD40732b_lo0002/PD40732b_lo0002.v1.sample.dupmarked.bam | grep -m 1 -n mm:A:Y)'
$ echo $?
124