How do I work around the fact that AWS SQS is not HIPAA compliant?
According to Amazon AWS


  Customers may use any AWS service in an account designated as a HIPAA
  account, but they should only process, store and transmit PHI in the
  HIPAA-eligible services defined in the BAA. There are ten
  HIPAA-eligible services today, including AWS Snowball, Amazon
  DynamoDB, Amazon EBS, Amazon EC2, Amazon Elastic MapReduce (EMR),
  Amazon Elastic Load Balancing (ELB), Amazon Glacier, Amazon Relational
  Database Service (RDS) [MySQL, Oracle, and PostgreSQL engines only],
  Amazon Aurora [MySQL-compatible edition only], Amazon Redshift, and
  Amazon S3.


source: https://aws.amazon.com/compliance/hipaa-compliance/

This means that as long as you are not storing or transmitting PHI in SQS, just the information about where this PHI is being stored - you probably can pass an audit reg. HIPAA compliance.

In the architecture you describe, the SQS queue does not need to include any PHI content. This would make it comply with the above statement.

More information about HIPAA compliance on AWS is available in this whitepaper from January 2017 - https://d0.awsstatic.com/whitepapers/compliance/AWS_HIPAA_Compliance_Whitepaper.pdf

Specifically SQS is mentioned and explained in the HIPAA FAQ - https://aws.amazon.com/blogs/security/frequently-asked-questions-about-hipaa-compliance-in-the-aws-cloud-part-two/.

update: As of May 1st 2017, SQS is now HIPAA compliant. https://aws.amazon.com/about-aws/whats-new/2017/05/amazon-simple-queue-service-sqs-is-now-a-hipaa-eligible-service/