Personally, I would implement the queue in both, PHP and Perl. The easiest approach would be in my opinion to have PHP append the new jobs to a text file, for example one JSON-encoded line per job, or to have PHP insert new jobs into a database table. Perl can then remove jobs either via Tie::File for the file approach or via DBI for the database approach.

There is Queue::DBI, which does most of the queue stuff for the Perl side of things. It could be easier to do the queue-appending from Perl if you can't convert the relevant parts of Queue::DBI to PHP easily.