PostgreSQL - Datetime ranges overlap
I suggest a couple of important improvements for dealing with a million rows:

SELECT br.duration
FROM  (
   VALUES 
      ('[2016-09-06 03:45:00+00, 2016-09-06 14:45:00+00)'::tstzrange)  
    , ('[2016-09-06 14:45:00+00, 2016-09-06 15:45:00+00)')
      -- more items
   ) br(duration)
WHERE EXISTS (
   SELECT FROM booking
   WHERE  tstzrange(ts_start, ts_end) &amp;&amp; br.duration
   );



While providing your list of values with the needlessly verbose and expensive form SELECT ... UNION ..., make that UNION ALL, or Postgres will waste time trying to fold duplicates. And you would only need to declare column name(s) and data type(s) for the first SELECT of the UNION query.
But a VALUES expression is simpler and faster. Or provide an array tstzrange[] and use unnest():


Optimizing a Postgres query with a large IN

The query you have would return one row for every overlapping row in booking, while you probably want each overlapping value from the list once, most likely. You could add DISTINCT or GROUP BY to get unique rows, but that would still be a waste of time. An EXISTS semi-join is one of the much simpler and cheaper alternatives for your case: Each row from duration is returned exactly once if an overlapping entry is found and Postgres can stop looking further for this row.
The query would still be slow without index support. Create a functional GiST or SP-GiST index. The latter probably performing best:

CREATE INDEX booking_ts_range_idx on booking USING spgist (tstzrange(ts_start, ts_end));



Related:


Optimizing queries on a range of timestamps (two columns)
Native way of performing this hours of operation query in PostgreSQL
Help with adding a time filter to Postgres query
Perform this hours of operation query in PostgreSQL (incl. SP-GiST index example and benchmark comparing alternatives)