Say $\mathcal{C}$ is a strict monoidal abelian category and $A$ is a *coalgebra* object in $\mathcal{C}$, with left co-modules $M$ and right co-module $N$ (also in $\mathcal{C}$). Then we have a notion of (derived) tensor product $$M\overset{R}{\otimes} {}^{co}\_A N,$$ (note that we are taking a right derived functor because we are in the co-situation of the left derived functor for usual tensor product), which can now be resolved as $$M\otimes\_{\mathcal{C}}N\to M\otimes\_{\mathcal{C}}A\otimes\_{\mathcal{C}}N\to \ldots\to M\otimes\_{\mathcal{C}}A\otimes\_{\mathcal{C}}\cdots\otimes\_{\mathcal{C}}A\otimes\_{\mathcal{C}}N\to \ldots$$ with maps given by comultiplication and coaction. (Here I'm assuming all objects involved are flat with respect to taking tensor product in $\mathcal{C}$). 


Now say that $\mathcal{C}$ is the monoidal category of $R$ bimodules for some (associative, not necessarily commutative) *algebra* R. Then the expression above reads 
$$M\otimes\_{R}N\to M\otimes\_{R}A\otimes\_{R}N\to \ldots\to M\otimes\_{R}A\otimes\_{R}\cdots\otimes\_{R}A\otimes\_{R}N\to \ldots.$$
The key point that I want to point out is that this complex uses the entire $R$-bimodule structure on $A$ (and its compatibility with comultiplication), but only half of the $R$-bimodule structure on $M$ and $N$. In particular, such an operation would be defined for any right $A$-comodule $M$ with just **right** $R$-module structure and left $A$-comodule $N$ with just **left** $R$-module structure, so long as the $A$-comodule structures and $R$-module structures satisfy some compatibility. For any such pair $M$, $N$ it should be possible to write down $$M\overset{?}{\otimes} N$$ computed by the same complex.


I'm curious about a formal algebraic setting that captures this data. Note that one thing I could do, given a right $A$-comodule $M$ with compatible right $R$-action and a left $A$-comodule $N$ with compatible left $R$-action would be to form the $A$-co-bimodule $$N\otimes\_k M$$ (which would now be an $R$-bimodule) and take its co-Hochschild homology $$M\overset{?}{\otimes} N: = \operatorname{coHH}\_\*^{R\mathrm{-Bimod}}(A, N\otimes M).$$ However, this doesn't quite satisfy me since it loses the separate nature of $M$ and $N$. It feels like there should be some other algebraic structure at play that is perhaps a generalization of something in the theory of Hopf algebroids. What is it?



Variant of co-Tor in a bimodule category
I am not sure that I really understand what you want, but I'd say the relevant structure is that of a module category over a monoidal category. Given a monoidal category $\mathcal E$, one can consider left and right module categories over it. For example, given an associative ring $R$, the category $\mathcal E=R\mathrm{-mod-}R$ of $R$-$R$-bimodules is a monoidal category. The category $\mathcal M=R\mathrm{-mod}$ of left $R$-modules is a left module category over $\mathcal E$ (with respect to the operation of tensor product over $R$). The category $\mathcal N=\mathrm{mod-}R$ of right $R$-modules is a right module category over $\mathcal E$.


It seems that there is a reasonably extensive literature about module categories over tensor categories. I am not familiar with this literature, but a simple Google search brings some papers or preprints. Let me give just this reference to an apparently relevant MO question -- [What is known about module categories over general monoidal categories?](https://mathoverflow.net/questions/6775/what-is-known-about-module-categories-over-general-monoidal-categories)


Now, if you are interested in derived (co)tensor products, then the following setting seems to be adequate. Let $\mathcal E$ be a monoidal category, $\mathcal M$ and $\mathcal N$ be a left and a right module category over $\mathcal E$, and $\mathcal K$ be an abelian category (or at least a category with (co)equalizers). Suppose that we are given a pairing functor $\otimes:\mathcal N\times\mathcal M\longrightarrow\mathcal K$ with an associativity constraint (natural isomorphism in $\mathcal K$) $$N\otimes (E\otimes M)\cong (N\otimes E)\otimes M$$ for all $N\in\mathcal N$, $E\in\mathcal E$, and $M\in\mathcal M$.


Then, given an associative (and, preferably, unital) algebra object $A\in\mathcal E$, one can speak about left $A$-module objects in $\mathcal M$ and right $A$-module objects in $\mathcal N$. Given two such objects $M$ and $N$, one can construct their tensor product $N\otimes\_AM\in\mathcal K$ as the coequalizer of the pair of arrows $$N\otimes A\otimes M\rightrightarrows N\otimes M.$$


In the above example with $\mathcal E=R\mathrm{-mod-}R$, $\mathcal M=R\mathrm{-mod}$, $\mathcal N=\mathrm{mod-}R$, you can take $\mathcal K$ to be the category of abelian groups (or the category of modules over any commutative ring $k$ such that $R$ is a $k$-algebra).


Given a quadruple of categories $(\mathcal E,\mathcal M,\mathcal N,\mathcal K)$ as above and an associative algebra object $A$ in $\mathcal E$, you can consider a new quadruple of categories $({}\_A\mathcal E\_A,\,{}\_A\mathcal M,\,\mathcal N\_A,\,\mathcal K)$, where ${}\_A\mathcal E\_A$ is the category of $A$-$A$-bimodules in $\mathcal E$, $\ {}\_A\mathcal M$ is the category of left $A$-modules in $\mathcal M$, etc. The functors of tensor product over $A$ will potentially make this into another quadruple of the same kind, with a monoidal category ${}\_A\mathcal E\_A$, two module categories over it, and a $\mathcal K$-valued pairing between them.


But associativity of such tensor products does not come for free. If you try to prove it in such a general setting, you will see that it depends on exactness properties of the tensor product functors in the original quadruple $(\mathcal E,\mathcal M,\mathcal N,\mathcal K)$. In particular, the functors of cotensor product of (bi)comodules over a coring over a (nonsemisimple) ring do not seem to be associative, generally speaking.


You can find a discussion of this setting on the second page of the introduction to my book "Homological algebra of semimodules and semicontramodules" (Monografie Matematyczne IMPAN vol.70, Birkhauser/Springer Basel, 2010, arXiv version available at <https://arxiv.org/abs/0708.3398> , but the publisher's version is more complete).


