Excellent question. This is a classic problem in parameterized complexity that sits at the intersection of structural graph theory and logic.

The short answer is: The problem is W[1]-hard, parameterized by .

Let's break down why this is the case, building on the results you've already found.

The XP Upper Bound

You correctly found the result by Grohe (from "The complexity of homomorphism and constraint satisfaction problems seen from the other side", JACM 2007) which implies that for a fixed integer , the problem is solvable in polynomial time. The algorithm is based on dynamic programming over the tree decomposition of .

A simplified version of the DP state for a bag of the tree decomposition of would be the set of all valid partial homomorphisms from the subgraph induced by to . Since , there are at most such partial homomorphisms. The total running time is roughly of the order .

If we also assume has treewidth at most , this does not fundamentally change the algorithm. The runtime remains polynomial in the sizes of and , but with an exponent depending on . This is the definition of an XP (slice-wise polynomial) algorithm. An algorithm is in XP if its runtime is , where is the input size and is the parameter. An FPT algorithm would require a runtime of for some constant . The existence of an XP algorithm leaves the question of FPT vs. W[1]-hardness open.

The W[1]-Hardness Result

The reason the problem is not FPT is that even a very structured target graph (e.g., one with small treewidth) can be used to encode a hard problem. The W[1]-hardness is a highly non-trivial result that builds upon several key ideas in parameterized complexity.

1. Hardness for General Target Graphs: Dániel Marx showed in 2007 ("A parameterized view on restricting the ‘left-hand side’ of the homomorphism problem") that the problem is W[1]-hard, parameterized by . This is the problem where has treewidth at most , but can be any graph. The proof is typically a reduction from the Multicolored Clique problem, which is a canonical W[1]-complete problem. In this reduction, the constructed graph has small treewidth (depending on the parameter of the clique instance), but the target graph is essentially the (large, unstructured) input graph from the clique problem, and thus has unbounded treewidth.

2. Hardness for Bounded Treewidth Target Graphs: This is the crucial part for your question. Does the hardness hold if we also require to have treewidth at most ? The answer is yes.

   The reduction from Multicolored Clique can be modified to produce a target graph that also has small treewidth (e.g., treewidth 2 is sufficient). The essential idea is to "encode" the structure of the arbitrarily complex graph from the original reduction into a new, highly structured graph of low treewidth. The source graph is then also modified so that any homomorphism can "decode" this structure and would correspond to a solution to the original hard problem.

   This result is considered a standard but advanced result in the field.

   • It is mentioned in surveys, for instance, in Martin Kreutzer's survey "Algorithmic Meta-theorems", he states that the W[1]-hardness of homomorphism parameterized by the treewidth of holds "even if the host graph H is restricted to have treewidth 2."
   • The influential textbook "Parameterized Algorithms" by Cygan, Fomin, et al. (2015) presents the W[1]-hardness proof for general (Theorem 13.5) and then leaves the modification for the bounded treewidth case as an exercise (Exercise 13.6):

     Exercise 13.6: Show that Homomorphism remains W[1]-hard parameterized by even if we require that .

The proof of this is quite technical, but it follows a pattern common in parameterized complexity for proving hardness on restricted graph classes like planar graphs or bounded-treewidth graphs. You essentially replace the unstructured hard graph with a structured "grid-like" or "tree-like" gadget that simulates it.

Summary of a Complex Landscape

To place your question in the broader context:

• parameterized by : W[1]-hard, even if . (This is your problem)
• parameterized by : FPT. (This is a classic result, mentioned in Flum & Grohe's book). The runtime is roughly , which is FPT.
• for a fixed graph (i.e., ), parameterized by : FPT. This is a special case of the more general result on counting homomorphisms, , which is FPT as you noted. When is fixed, its structure can be exploited by the algorithm.
• parameterized by : FPT. If the size of is part of the parameter, the term in the DP becomes a function of the parameter, leading to an FPT algorithm.

Your problem hits the difficult case where both and can be large, and the only structural promise is the treewidth bound , which is the parameter. This turns out to be insufficient to avoid a combinatorial explosion dependent on the parameter, making the problem W[1]-hard.