Merge Join Performance Tuning
The issue with the SQL appears to be a Merge Join...


The optimizer's estimate is that the Merge Join will account for 85.8% of the cost of running the query, but you should always treat these figures with a healthy degree of suspicion.

They are just estimates based on a fairly simple costing model that helps the optimizer make general choices between alternatives, but the numbers almost certainly do not correlate with the performance characteristics of the execution plan on your particular hardware. The cost estimates are a broad hint at things the optimizer felt were costly, but there's no substitute for analysis by a skilled and experienced database professional.

That said, the main reason for the optimizer's high cost estimate for the merge join in this case is that the join is assumed to be many-to-many. This is because the database schema does not provide any constraints or unique indexes to guarantee a one-to-many relationship. The assumed many-to-many join is also the reason for the outrageously high join output cardinality estimate. Given incomplete information, the optimizer produces an inaccurate estimate.

The question does not provide schema DDL for the tables involved, but we can infer some of the columns from the execution plan, and something about the relationships from the joins. The data types are unknown for the most part, and we cannot know about foreign keys or other constraints, of course.

An update to the question while I was writing this answer states that the query cannot be changed, but for the sake of analysis, I had already rewritten it to at least use modern JOIN syntax:

SELECT
    a.wf_state, 
    b.oid, 
    p.wf_user_id, 
    p.error_no, 
    item_followup = 1,
    p.element_type, 
    selected = 0,
    p.version_no, 
    p.p_description, 
    p.s_description, 
    p.proc_node_id, 
    p.step_node_id, 
    p.distr_type, 
    f.project, 
    d.reg_period, 
    d.resource_id, 
    d.last_update, 
    a.used_hrs 
FROM dbo.awfenquiry AS p
JOIN dbo.atstsehourdetmap AS b
    ON b.oid = p.oid
JOIN dbo.atstsehourdet AS a
    ON a.tsehourdet_id = b.tsehourdet_id
JOIN dbo.atstsegldetail AS c
    ON c.tsegldetail_id = a.tsegldetail_id
JOIN dbo.atstseheader AS d
    ON d.tseheader_id = c.tseheader_id
JOIN dbo.atschargecode AS e
    ON e.client = c.client
    AND e.chargecode_id = c.chargecode_id
JOIN dbo.atsproject AS f
    ON f.project = e.project
    AND f.client = e.client
WHERE
    p.element_type = N'TS' 
    AND a.client = N'GB' 
    AND 
    (
        a.wf_state = N'U' 
        OR p.distr_type = N'U' 
    );


One of the main improvements you can make is to give each table a clustered index. Almost all tables benefit from having a clustered index, either for space management reasons, or simply because it provides an extra 'free' index. In many cases, the clustered index will also be the primary key, though this is not required. All tables should have a key. Many people would argue that a table is improperly formed without one. As a starting point, I have given each table a primary key based on my best guess. The primary key is clustered by default.

Putting all that together, a first pass at a schema is:

CREATE TABLE dbo.awfenquiry -- p
(
    oid integer PRIMARY KEY,
    element_type nvarchar(50) NULL,
    wf_user_id integer NULL,
    error_no integer NULL,
    version_no integer NULL,
    p_description nvarchar(50) NULL,
    s_description nvarchar(50) NULL,
    proc_node_id integer NULL,
    step_node_id integer NULL,
    distr_type nvarchar(10) NULL
);

CREATE TABLE dbo.atstsehourdetmap -- b
(
    oid integer NOT NULL,
    tsehourdet_id integer NOT NULL,

    PRIMARY KEY (oid, tsehourdet_id)
);

CREATE TABLE dbo.atstsehourdet -- a
(
    tsehourdet_id integer PRIMARY KEY,
    tsegldetail_id integer NULL,
    wf_state nvarchar(10) NULL,
    used_hrs integer NULL,
    client nvarchar(10) NULL
);

CREATE TABLE dbo.atstsegldetail -- c
(
    tsegldetail_id integer PRIMARY KEY,
    tseheader_id integer NULL,
    client nvarchar(10) NULL,
    chargecode_id integer NULL
);

CREATE TABLE dbo.atstseheader -- d
(
    tseheader_id integer PRIMARY KEY,
    reg_period integer NULL, 
    resource_id integer NULL, 
    last_update datetime2 NULL, 
);

CREATE TABLE dbo.atschargecode -- e
(
    chargecode_id integer NOT NULL,
    client nvarchar(10) NOT NULL,
    project integer NULL,

    PRIMARY KEY (chargecode_id, client)
);

CREATE TABLE dbo.atsproject -- f
(
    project integer NOT NULL,
    client nvarchar(10) NOT NULL,

    PRIMARY KEY (project, client)
);


Statistics were not provided either, but we can at least see the overall table cardinalities in the execution plan. The following statements provide this information for the table definitions above, without any information about value distribution:

UPDATE STATISTICS dbo.awfenquiry WITH ROWCOUNT = 51826;
UPDATE STATISTICS dbo.atstsehourdetmap WITH ROWCOUNT = 2748620;
UPDATE STATISTICS dbo.atstsehourdet WITH ROWCOUNT = 2743040;
UPDATE STATISTICS dbo.atstsegldetail WITH ROWCOUNT = 1223270;
UPDATE STATISTICS dbo.atstseheader WITH ROWCOUNT = 328822;
UPDATE STATISTICS dbo.atschargecode WITH ROWCOUNT = 23983;
UPDATE STATISTICS dbo.atsproject WITH ROWCOUNT = 18169;


Based on the query, there are few obvious index candidates beyond the keys already added. Two that may be of use are:

CREATE NONCLUSTERED INDEX i 
ON dbo.awfenquiry (element_type);

CREATE NONCLUSTERED INDEX i 
ON dbo.atstsehourdet (client) 
INCLUDE (wf_state, tsegldetail_id, used_hrs);


The resulting execution plan is not obviously a massive improvement over the original, aside from the (now one-to-many) merge join, but it is a step in the right direction perhaps:



All the tables are relatively small, so I would probably check next to see if query execution is being blocked by another process, fighting for resources with other queries, or struggling with an overwhelmed storage system. Fifteen seconds seems entirely unreasonable for the task.