How many possible phone words exist for a phone number of length N when also counting words less than length N within that phone number? The phone words problem
find all possible words that can be derived from a phone keypad, "words" do not have to be English dictionary words, for this question, words can be any combination of letters which can be mapped from a digit. 
For those not familiar, phone keypads often have letters under most digits:
╔═════╦═════╦═════╗
║  1  ║  2  ║  3  ║
║     ║ abc ║ def ║
╠═════╬═════╬═════╣
║  4  ║  5  ║  6  ║
║ ghi ║ jkl ║ mno ║
╠═════╬═════╬═════╣
║  7  ║  8  ║  9  ║
║ pqrs║ tuv ║wxyz ║
╠═════╬═════╬═════╣
║  *  ║  0  ║  #  ║
║     ║     ║     ║
╚═════╩═════╩═════╝

Counting only phone words with length $n$
Here's an example to get an idea of the phone words problem: given a phone number 366, you could generate the following phone words 
"dmm", "dmn", "dmo", "dnm", "dnn", "dno", "dom", "don", "doo", "emm", "emn", "emo", "enm", "enn", "eno", "eom", "eon", "eoo", "fmm", "fmn", "fmo", "fnm", "fnn", "fno", "fom", "fon", "foo"

Because 3 can be replaced by either "d", "e" or "f", and 6 can be replaced by either "m", "n" or "o". The upper bound on the number of phone words of length $n$ for a number with $n$ digits is $4^n$ (most keys have 3 letters but 7 and 9 both map to 4 letters).
Counting all words up to and including length $n$
The example above gives us 27 words, but we were only counting words whose length equals the number of digits of the phone number 366. What if we want to find all words including those whose length is less than the phone number? For example,  given the same input as before, 366, you could also have generated words "no", "on", "n", etc.... How many total phone words can be generated for a phone number of length $n$? 
To put this another way
Given a phone number of length $n$, we can generate $4^n$ phone words of length $n$, we can also generate $2(4^{n-1})$ phone words for each sub phone number with length $n-1$ (using the example above, that would be all phone words of 36 and 66), then all phone words for all possible sub phone numbers of length $n-2$ etc.. How many phone words are there for a phone number of length $n$ if we count all phone words possibilities or all lengths less than $n$? 
Attempt at an answer
Attempting to string the above description into an equation:
$W = 4^{n} + 2(4^{n-1}) + 3(4^{n-2}) + \ldots + n$
But not sure where to go with this.
Terminology
Phone number is an ordered sequence of numerical digits. Example: 1234560, 366 etc... 
Phone word is an ordered sequence of latin alphabetical characters (found on En-US telephone key pads). 


*

*Each phone word can be directly mapped to exactly one phone number of the same length. For example: "foo" can be mapped to 366. 

*Each phone number may be mapped to zero or more phone words.


Sub phone number: Given a phone number, there are $n(n+1)/2$ ways to "slice" the number into smaller phone numbers (without changing the order of the numbers). For example: 366 contains the following sub phone numbers: 36, 66, 3, 6, 6
 A: Sometimes in problems like this, it's useful to consider algorithms that generate the answer. Consider the following python code:
def num_words(phone_number):
  n = len(phone_number)
  words = []
  for i in {0, ... , n - 2}:
    for j in {i + 1, ... , n - 1}:
      words += generate_words(phone_number[i:j])
  return words

Here s[i:j] produces the substring running from index i to index j and generate_words(s) returns a list of words creatable from exactly the string s, as you do in your first list of words. It should be clear that this code produces the list that you want, so now we just need to figure out how big the list "words" is. Let's assume every key has m letters on it, so that our formula gives us both a lower bound (at $m=3$) and an upper bound (at $m=4$). Converting directly from this program into a sum gives us $$\sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}|S_{i,j}|$$ where $S_{i,j}$ is the list given by the generate words function called on a string running from index i to index j.
This is a common visualization technique in combinatorics, as computer programs that answer questions tend to make it clear how subproblems are iterated over. At each step in the program, however many words are in the list "generate_words(phone_number[i:j])" get added to the total list of words, so at every step of the sum we should be adding the corresponding quantity, which is defined to be $|S_{i,j}|$. When counting the total number of words, the for loops convert directly into summation symbols with the same bounds of summation due to the "+=".
Notice that the value of $|S_{i,j}|$ doesn't actually depend on $i,j$'s values, merely their difference. This gives us the formula (remember, assuming every key has $m$ letters): $$\sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}m^{j-i}=\frac{m(m^n-mn+n-1)}{(m-1)^2}$$
Where the value of the sum is computed via Wolfram Alpha. Plugging in our values of $m$ to get upper and lower bounds yields $\frac{3}{4}(3^n-2n-1)\leq N \leq \frac{4}{9}(4^n-3n-1)$. Obtaining precise values is likely to be very hard, as introducing an indicator function for a character having options of being 4 (instead of 3) letters makes the sum impossible to simplify meaningfully, as it's rather sensitive to the exact positioning of $4$ letter numbers within the broader string.
The above implicitly assumes $n>1$, so we can separately note that the answer for $n=1$ is $m$ (as both an upper and a lower bound).
A: I'll reestablish some of the things you've already stated, so that the argument is a bit more complete.
Note that I will only establish a strict upper and lower bound for the amount of phone words (as defined by you).

For each phone number $p_n$ of length $n$ there are $2$ sub-numbers of length $n-1$. Each of these have $2$ sub-numbers of length $n-2$. However, at least two of them are identical (consider for instance $\{3415, \{341, 415\}, \{34, 41, 41, 15\}\}$. Consequently the count of distinct sub-numbers of length $n-2$ is 3. By induction this behaviour continues.
Let $w_n$ be the upper bound of the amount of all phone words of length $\ell =n$ we can generate with a phone-word of length $n$. Obviously 
$$w_n = 4^n$$
Let then $W_n$ be the upper bound of the amount of all phone words of length $\ell \in [1, n]$ we can generate with phone-word of length $n$. Now we get
$$W_n = w_n + 2\cdot w_{n-1} + 3 \cdot w_{n-2} \dots = \sum_{k=1}^{n} (n-k + 1)\cdot 4^k = (n+1)\sum_{k=1}^{n}4^k - \sum_{k=1}^{n}k\cdot4^k$$
The first series is a plain geometric series, the second one is a bit more tricky, I am in fact not sure how to solve it, but my favorite CAS gave me the following result:
$$\begin{align} W_n &= (n+1)\sum_{k=1}^{n}4^k - \sum_{k=1}^{n}k\cdot4^k = (n+1)\cdot\underbrace{\frac{4}{3}(4^n - 1)}_{\text{First sum}} - \underbrace{\frac{4}{9}(1-4^n+3\cdot 4^n\cdot n)}_{\text{Second sum,  magic}} \\
\end{align}$$
Note that you didn't ask for it but I'll just note what the lower bound is, as we've found an upper bound. The lower bound , call it $\omega_n$ occurs when a phone number is a sequence of repeating digits not equal to $7$ or $9$. It then only has $1$ unique sub number, and consequently:
$$\omega_n = 3^n + 3^{n-1} \dots = \sum_ {k=1}^{n}3^k = \frac{3}{2}(3^n - 1)$$
A: There are a few ways to interpret the question, but chiefly I see two:


*

*Given a specific phone number $d_1, d_2, \dots, d_n$, with $d_i$ digits between $0-9$, how many "phone words" does it contain. More precisely, take the set of all non-empty words over the $26$ letter alphabet. An $m$ letter word $w$ in this set can be represented by $c_1, c_2, \dots, c_m$, where each $c_i$ is one of the $26$ letters. We then say a number $d_1, d_2, \dots, d_n$ "contains" a word $c_1, c_2, \dots, c_m$ with iff there is some $1 \leq i \leq j \leq n$ such that $d_i, d_{i+1}, \dots, d_j$ matches $c_1, c_2, \dots, c_m$. We say that a string of digits "matches" a string of characters (a word) iff typing that string of digits on a phone keypad can result in that word (a more precise definition is possible, but not necessary I think).

*Given the set of all phone numbers of length $n$, starting at $\overbrace{0, 0, \dots, 0}^\text{$n$ times}$ and ending at $\overbrace{9, 9, \dots, 9}^\text{$n$ times}$, how many phone words are there such that there exists some phone number in our set that contains the word? Contains is in the same sense as above.
I believe the other questions address case $(1)$, which is by far the harder case. For completeness, I will answer case $(2)$ here, but I warn a reader of this post that the answer is not very exciting. We simply observe that any word of length less than $n$ is contained in some number of length $n$. In fact, it is contained in many a number. To construct just one of these numbers, simply type the numbers on the phone keypad corresponding to the given word, and fill in the rest with whatever you like. Thus the question reduces to: how many words of length $n$ or less can be formed from the $26$ letter alphabet? There are $26$ one letter words, $26^2$ two letter words, $26^3$ three letter words, and so on. So the answer is simply the geometric sum:
$$26 + 26^2 + \dots + 26^n = \dfrac{26^{n+1} - 26}{25}$$
