Parabolic convolution of perverse sheaves in terms of the Hecke algebra It is "well-known" that the Hecke algebra $\mathcal{H}$ can be thought
of as the Grothendieck group for the category of perverse sheaves on
$G/B$, where the product in $\mathcal{H}$ corresponds to convolution
of sheaves by the Borel subgroup.  This means, given perverse sheaves
$X$ and $Y$ on $G/B$ and their classes $[X]$ and $[Y]$ in the
Grothendieck group considered as elements of $\mathcal{H}$, the
element $[X][Y]$ is (the class of) the sheaf
$$q_B(\pi^*(X)\boxtimes Y),$$
where $\pi$ is the quotient map $G\rightarrow G/B$ and $q_B$ is the
operation that takes a sheaf on $G\times G/B$ which is equivariant
under the action of $B$ by $b\cdot (g, hB) = (gb^{-1}, bhB)$ and
quotients out by this action, mapping to a sheaf on $G/B$.
Now I want to think about convolution using a parabolic subgroup
larger than the Borel.  Suppose $P$ is a parabolic, $X$ is a perverse
sheaf on $G/B$ which is pulled back from $G/P$, and $Y$ is $P$-equivariant.
What is the class of
$$q_P(\pi^*(X)\boxtimes Y),$$
where $q_P$ now quotients by the action of $P$ by $p\cdot (g, hB) =
(gp^{-1}, pHB)$ in terms of the Hecke algebra?
Motivation: Actually, I only care about the case where $X$ and $Y$ are
IC sheaves of Schubert varieties, so $[X]$ and $[Y]$ are
Kazhdan--Lusztig basis elements.  In this case, by the Decomposition
Theorem the product will give a positive, bar--invariant sum of
Kazhdan--Lusztig basis elements, so if you find good choices of $X$
and $Y$ and understand this product, you get a good inductive method
for calculating Kazhdan--Lusztig polynomials.  In some cases I am
interested in, I have calculated the product geometrically by
localization, but sticking to algebra would make things cleaner and
likely easier to write up in general.  There are cases in which this
has been done, most notably Polo's paper showing that any polynomial
with positive integer coefficients and constant term 1 is a
Kazhdan--Lusztig polynomial; an answer to this question should allow
one to dispense with geometry in his paper and formulate his
calculations entirely within the Hecke algebra (given a theorem that
says the algebraic analogue of parabolic convolution produces positive sums of Kazhdan--Lusztig elements).
Although everything makes sense for an arbitrary Kac-Moody group, I am
happy with an answer for the finite dimensional case, or even with
answers for type A.
Pre-emptive requests: (1) I expect parabolic Kazhdan--Lusztig elements
will come up.  As there are several variants, please tell us which one
you mean, with reference to a paper using your notation.  (2) As you
may have noted from my vague description of $q_B$ and any other
mistakes I might have made above, I don't really understand perverse
sheaves and intersection cohomology.  Please feel free to correct me,
and please give me an answer I can understand.
 A: Let $G$ be a connected reductive algebraic group (over $\mathbb{C}$) and fix a Borel subgroup $B \subset G$. One can consider the 2-category with objects parabolic subgroups $P \supset B$ and 1-morphisms $P \to Q$ given by $D^b_{P\times Q}(G)$ (the $P \times Q$-equivariant derived category of $G$ with respect to the action $(p,q) \cdot g = pgq^{-1}$ for $p \in P$, $q \in Q$ and $g \in G$). 2-morphisms are the morphisms of $D^b_{P \times Q}(G)$. Composition of 1-morphisms is given by convolution:
$* : D_{P \times Q}(G) \times D_{Q \times R}(G) \to D_{P \times R}(G)$
(you can probably guess how this is defined using the description you give above). 
Then your question is a special case of the following question:
Q: describe the Grothendieck group of this 2-category (a 1-category).
The answer is that Grothendieck group is* what I call the Schur algebroid (for want of a better name). See the beginning of my paper "Singular Soergel bimodules" on the arXiv. (I am only referring to my paper because it is a convenient reference. Certainly these things have been known to experts since at least the early 80's.)
If you would prefer not to look at this paper here is a direct answer to your question. For any subset $I \subset S$ of the simple reflections let $\underline{H}_I$ denote the Kazhdan-Lusztig basis element indexed by the longest element of the standard parabolic $W_I$. Then, given $h \in \mathcal{H}\underline{H}_I$ and $h' \in \underline{H}_I \mathcal{H}$ one can define
$h*_I h' := \frac{1}{\pi(I)} hh'$
where $\pi(I)$ denotes the Poincaré polynomial of $W_I$. (Note that this element really lives in the $\mathbb{Z}[v,v^{-1}]$ form of the Hecke algebra.) This is the class in the Hecke algebra you are looking for.
*: Of course this is not true because one has lost the $q$: what I really mean is that one should either consider the split Grothendieck group of semi-simple complexes (or parity sheaves if one prefers) or use an appropriate mixed version.
Final note: you talk about Polo's result about arbitrary polynomials $ \in 1 + q\mathbb{N}[q]$ occuring as KL-polynomials. I recall that there is a purely combinatorial proof of this result in the literature. Unfortunately I can't remember the title or author, but it shouldn't be difficult to find.
