The method **joro** suggests works with little change for any $(k,m)$.

Fix an elliptic curve $E: P(X,Y)=1$ of positive rank.
Some simple examples are
$F(X,Y) = Y^2 - X^3 + 2X$ and $F(X,Y) = Y^2 - X^3 - 2$,
each with generator $(X,Y)=(-1,1)$.

Let $u$ and $v$ be "random" rational functions on $E$
that generate the function field (almost any choice will work, see below).
Then $u$ and $v$ satisfy a minimal equation $g(u,v)=0$
which defines an algebraic curve birational to $E$
and thus has infinitely many rational solutions.

Set $x = u^k$ and $y = v^m$.  As long as these functions, too,
generate the function field of $E$, the equation $f(x,y)=0$
that they satisfy gives an irreducible elliptic curve
with infinitely many rational points at which $x$ is a $k$-th power
and $y$ is an $m$-th power.  To check this it is enough to verify
that the map $(X,Y) \mapsto (x,y) = (u^k,v^m)$ is generically
injective on $E$, and for *that* it's enough to find one point
$(u,v)$ on $E$ such that there's no other $(u',v') \in E$
with ${u'}^k=u^k$ and ${v'}^m = v^m$.  For some $k$ and $m$
we can even to take $(u,v) = (X,Y)$, and in general
a pair of "random" translates $(X+u_0, Y+v_0)$ should suffice.

The polynomial equation $f(x,y) = 0$ can be computed by
eliminating $u,v$ from the system $g(u,v) = u^k-x = v^m-y = 0$:
take the resultant of the first two equations with respect to $u$
to obtain a relation between $v$ and $x$, and then take the resultant
w.r.t. $v$ of that relation and $v^m-y$.

For example, applying this recipe to $Y^2 = X^3 + 2$ with
$(k,m)=(11,7)$ and $(u,v)=(X,Y)$ yields the irreducible polynomial

> x^21 + (-36960*y^2 + 14336)*x^18 + (154*y^6 + 396506880*y^4 + 19029491712*y^2 + 88080384)*x^15 + (12029248*y^8 - 1216366964736*y^6 + 284451691560960*y^4 - 391801278038016*y^2 + 300647710720)*x^12 + (5236*y^12 + 41292382208*y^10 + 649374955536384*y^8 + 261188560760078336*y^6 + 4032263773430480896*y^4 + 1338427807910330368*y^2 + 615726511554560)*x^9 + (-61949888*y^14 + 5483890384896*y^12 - 20842181162958848*y^10 + 8440505090430730240*y^8 - 456851090435200778240*y^6 + 2810028717064564244480*y^4 - 898304588698945060864*y^2 + 756604737398243328)*x^6 + (16016*y^18 + 1301780480*y^16 + 5890099511296*y^14 + 5689217111818240*y^12 + 1688064484691673088*y^10 + 172250320914033410048*y^8 + 5873494991874845310976*y^6 + 55086593993714775883776*y^4 + 78432673497651496353792*y^2 + 516508834063867445248)*x^3 + (-y^22 + 1408*y^20 - 901120*y^18 + 346030080*y^16 - 88583700480*y^14 + 15874199126016*y^12 - 2031897488130048*y^10 + 185773484629032960*y^8 - 11889503016258109440*y^6 + 507285462027012669440*y^4 - 12986507827891524337664*y^2 + 151115727451828646838272)

vanishing on infinitely many pairs $(x,y) = (X^{11},Y^7)$.